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

• Are you considering that $a$ and $b$ are primes smaller than $n$? Commented Aug 14, 2017 at 10:59
• en.wikipedia.org/wiki/Integer_factorization Commented Aug 14, 2017 at 14:51

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) Commented Aug 14, 2017 at 14:19
• Should add that $b^{-1}\mod{n}$ is efficiently computable using the extended Euclidean algorithm. Commented Aug 14, 2017 at 14:46