Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas.

Is there an analog of the elliptic curve (ECM) factoring algorithm, but for discrete logs? Something that uses similar ideas, but can be used to compute discrete logs modulo $p$?

  • $\begingroup$ It is kind of equivalent. If you take m = bi n = bj and compute mn mod p, finding i+j is the discrete log. So if you can factor mn mod p, where one factor is a known power of b, that reduces the problem to determining the exponent of the other factor, which is by definition smaller (outside of its congruence class mod p). $\endgroup$ Jan 31 '13 at 8:48
  • $\begingroup$ @CrisStringfellow, thanks for the thought, but that is not correct: your method does not work. The error in your reasoning is in the part where you say "which is by definition smaller". To discover the error for yourself, try writing out the exact reduction: an algorithm which computes the discrete logarithm, given a magical black box that factors any integer of your choice. Then, try to analyze the running time of your scheme. I think you'll find your method doesn't work. $\endgroup$
    – D.W.
    Jan 31 '13 at 19:20
  • $\begingroup$ The exponent of a factor of g (g = b**k) is smaller than k. $\endgroup$ Jan 31 '13 at 19:24
  • $\begingroup$ @CrisStringfellow, I assure you, your method does not work. A full explanation of why it doesn't work is beyond the scope of this comment thread. But I'll give you a hint. Suppose we have $g=b^k \bmod p$, and we factor the integer $g$ into the factors $g=ef$. It is simply not true that the discrete log of $e$ will always be smaller than $k$. And that's all I'm going to say on this subject. If you want to understand this further, please ask a different question, rather than posting comments here. Further comments on this subject are likely off-topic. $\endgroup$
    – D.W.
    Feb 1 '13 at 6:56

Similar algorithms for factoring and discrete log are limited to pollard rho and sieve methods using a factor base. There are other factoring methods such as square forms, p+1 and ECM which as far as I know don't have logarithm-in-$F_p$-finding analogues. The factoring methods rely (explicitly for rho and implicitly for sieve methods) on treating a ring like a field, trying to measure the order of elements and waiting for the process to break down. Calculating a discrete log is a very similar process but it works correctly. The other way to answer your question is yes there is a logarithm-finding analogue of ECM but it finds elliptic-curve logarithms. Similarly,the logarithm-finding analogue of Williams' p+1 method finds logarithms in a quadratic field. Not what you had in mind I guess.


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.