# 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?

## 1 Answer

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}.$$

• Note that a prime in Z is not necessarily prime in Z/nZ, and conversely. – fkraiem Aug 14 '17 at 12:53
• @fkraiem: what does 'prime in Z/nZ' mean? I suppose it could be given a natural meaning, but that seems to be 'a prime factor of n (possibly multiplied by a value relatively prime to n)'; and it'll take longer than this comment to explain what that is the natural meaning... – poncho Aug 14 '17 at 13:20
• @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
• The private and public keys are inverses modulo a number which the adversary does not know. – fkraiem Aug 15 '17 at 4:00