Jump to content

Talk:Index calculus algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

[Untitled]

[edit]

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

[edit]

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.

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...

[edit]

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]

How to caluculate the log(p_i)?

[edit]

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]

But the logarithm is not unique?

[edit]

One can add a multiple of . — Preceding unsigned comment added by 109.90.224.162 (talk) 13:37, 28 September 2015 (UTC)[reply]