# Is factorization modulo a product of primes an NP-hard problem?

For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$. Now, let $a \cdot b = c \pmod n$. Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult?

I can alternatively ask, is integer factorization modulo a product of primes an NP-hard problem?

Your question has not a unique answer. In general case, finding $a,b$ is very simple. In this state, we can choose an arbitrary $b$(can be a prime number) and find the $a$ as follow: $$a=c\cdot b^{-1} \pmod n.$$ Unfortunately, if you need that $a$ be prime, your question has no unique answer again. As an example, let $n=33$ and $c=20$. So we have: $$7\cdot17=23\cdot31=20 \pmod{33}.$$
• @AbdullahGani: you don't need to factor $n$ to compute $b^{-1} \bmod n$ for arbitrary $b$. The worse thing that could happen is that'll fail if $b$ happens not to be relatively prime to $n$ (which will essentially never happen if $n$ is an RSA modulus) – poncho Aug 14 '17 at 14:19
• Should add that $b^{-1}\mod{n}$ is efficiently computable using the extended Euclidean algorithm. – Occams_Trimmer Aug 14 '17 at 14:46