5
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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$
    – Cris Stringfellow
    Commented Jan 31, 2013 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.
    Commented Jan 31, 2013 at 19:20
  • $\begingroup$ The exponent of a factor of g (g = b**k) is smaller than k. $\endgroup$
    – Cris Stringfellow
    Commented Jan 31, 2013 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.
    Commented Feb 1, 2013 at 6:56

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Are there no subexponential methods whose complexity is determined by the known range of the resulting discrete logarithm? I m asking this since ecm can be faster for factoring in this way on very very large numbers. $\endgroup$
    – user2284570
    Commented Aug 21 at 10:11

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.