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)[reply]

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(2ⁿ), or generally GF(pⁿ) 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.

71.41.210.146 (talk) 12:29, 13 April 2008 (UTC)[reply]

Isn't the NFS a (vastly improved) variant of index calculus? So that while the statement might be misleading it is not completely wrong? caramdir (talk) 10:23, 6 April 2009 (UTC)[reply]

Super weak article...

BTW, AFAIK the GNFS is the exponentially fastest known algorithm for computing discrete logs (mod p). Nageh (talk) 18:26, 27 January 2010 (UTC)[reply]