2
$\begingroup$

I read in a document that for a given $n = p\times q$ ($p$, $q$ primes), if you know $p$ and $q$ then you can easily solve the discrete logarithm problem, i.e. for fixed $a,b$, you can find $x$ such that $$a^x = b \bmod n$$ But I don't see how this can be done... I tried to check if the Chinese reminder theorem could help me, and this reduces to find the discrete logarithm modulo $p$ and modulo $q$, but I still don't see how we can get this new discrete logarithm without bruteforcing (which is still exponential, even if you get a square root improvement over the naive bruteforce).

Thank you!

|improve this question
$\endgroup$
  • 1
    $\begingroup$ I'm sure you're right saying "[not] see[ing] how this can be done". Computational DL problem is hard for modulus with large prime factor(s), so you've probably mistaken it for discrete root problem. So could you tell us the title and the authors, or provide link for the document where you encounter such statement? $\endgroup$ – DannyNiu Apr 15 '19 at 7:55
  • $\begingroup$ @DannyNiu Oh great then, thanks! Well it was written in the correction of some tutorial I'm supposed to give (so nothing to do with a formal article), so I think the one that wrote the correction just wrote a wrong correction, especially because there is a much simpler solution to the question. Thank you! Feel free to write it as an answer if you want. $\endgroup$ – tobiasBora Apr 15 '19 at 8:00
  • $\begingroup$ If a generic algorithm costs $C \approx 2^{128}$, and knowledge of the factorization reduces that to $\sqrt C \approx 2^{64}$, don't you think that is a noteworthy improvement? Look up the Bitcoin hash rate, or the cost to Google of computing a SHA-1 collision, to put this scale in perspective. $\endgroup$ – Squeamish Ossifrage Apr 16 '19 at 2:55
2
$\begingroup$

This is not true in general. Bach showed that given the factorization of $n$, computing the discrete log modulo $n$ requires computing it modulo the factors (also cf. this previous question for more details.). So, if both the factors are large then DLP is still hard.

|improve this answer
$\endgroup$
1
$\begingroup$

The Pohlig-Hellman solves the DLP in time $O(\sqrt{p})$, where $p$ is the largest prime factor of the group you're working in. You're working in $\mathbb{Z}_n^*$, which has order $\varphi(n) = (p-1)(q-1)$, so if this factors into many small primes you have issues.

This is the basis behind Sophie Germain primes, which are primes of the form $q = 2p+1$, where $p$ is prime. This satisfy $\varphi(q) = 2p$, so they're "minimally smooth" (for any odd prime, we know that $2$ will divide $\varphi(q)$. Sophie Germain primes are primes where this is the only small divisor).

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If $q = 2p + 1$, then $q$ is a safe prime, not a Sophie Germain prime; $p$ is the corresponding Sophie Germain prime. $\endgroup$ – Squeamish Ossifrage Apr 16 '19 at 2:46

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.