Talk:Index calculus algorithm
What a great algorithm, and well described! It seems like the discrete logarithm of any number which is near a product of powers (in Z not Zq) of guessable factors can be found quite easily. If only we can get to step 10...
--jdb 67.127.185.246 08:33, 25 August 2007 (UTC)
Dubious
Although they're generally similar in run-time charactersitics, isn't the number field sieve actually faster for solving the duiscrete log in GF(p)? (See the Chris Studholme paper for a description; it's not just a factorization algorithm.) The index calculus algorithm is particularly fast for GF(2n), or generally GF(pn) for small p and large n, so it might beat out NFS there.
The index calculus algorithm has the great advantage that most of the computation is independent of the number to be solved for, so once you've completed stages 1 & 2, you can solve a particular discrete log problem quickly.