Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
It is kind of equivalent. If you take m = b**i n = b**j 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). –  Cris Stringfellow Jan 31 '13 at 8:48
    
@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. –  D.W. Jan 31 '13 at 19:20
    
The exponent of a factor of g (g = b**k) is smaller than k. –  Cris Stringfellow Jan 31 '13 at 19:24
    
@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. –  D.W. Feb 1 '13 at 6:56
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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