2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note that a prime in Z is not necessarily prime in Z/nZ, and conversely. $\endgroup$ – fkraiem Aug 14 '17 at 12:53
  • 4
    $\begingroup$ @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... $\endgroup$ – poncho Aug 14 '17 at 13:20
  • 2
    $\begingroup$ @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) $\endgroup$ – poncho Aug 14 '17 at 14:19
  • 2
    $\begingroup$ Should add that $b^{-1}\mod{n}$ is efficiently computable using the extended Euclidean algorithm. $\endgroup$ – Occams_Trimmer Aug 14 '17 at 14:46
  • 2
    $\begingroup$ The private and public keys are inverses modulo a number which the adversary does not know. $\endgroup$ – fkraiem Aug 15 '17 at 4:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.