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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
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}.$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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