Talk:Index calculus algorithm

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

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

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

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

Ok, most of this is clear, but how to find the values of the discrete logarithm of the small prime factors? — Preceding unsigned comment added by 109.90.224.162 (talk) 14:03, 24 September 2015 (UTC)Reply

One can add a multiple of ${\displaystyle \varphi =p-1}$. — Preceding unsigned comment added by 109.90.224.162 (talk) 13:37, 28 September 2015 (UTC)Reply