|WikiProject Mathematics||(Rated B-class, Mid-importance)|
Who found it?
Wasn´t it Shanks who found this algorithm? We called it "Shanks Babystep-Giantstep Algorithm". I´m not sure... but if it is so one should mention it.
Yes it was Shanks, and he initially used it to compute group orders, not discrete logarithms, although it can do both. This page needs work: Shanks should be more properly credited, the use of the algorithm to compute group orders should be explained, and at least some mention of various modifications to handle unbounded searches and optimizing for distribution should be made. The versatility of this algorithm makes it a workhorse that is used for all sorts of things besides computing discrete logarithms, and cryptography is but one of many applications (and not the first, Shanks was interested in computing the order of ideal class groups). The context of the current article is too narrow.
There is currently an unreferenced tag on the page, claiming that the page is not properly referenced. Isn't the reference to Shank's paper enough?775
Several references have been added.
I think there is a slight error in the algorithm's description
Step 3 says to compute a-m. But the original algorithm is to compute [a-1]m. In the modular world, a-1 means "the multiplicative inverse of a", and is not an exponent that you can actually multiply out. Can an expert on this algorithm please confirm this? 188.8.131.52 (talk) 21:04, 3 December 2008 (UTC)
- You are correct. There is no error in the description of the article. The equations in Theorem 1.9 of the section Elementary_group_theory#Powers are true for all integers. 184.108.40.206 (talk) —Preceding undated comment added 11:47, 25 July 2009 (UTC).
It is Fermat's theorem that states B^(P-1) == 1 (mod P)
for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat's theorem is that for any m
B^(-m) == B^(P-1-m) (mod P) . —Preceding unsigned comment added by 220.127.116.11 (talk) 11:59, 22 July 2010 (UTC)
GNU_MP code snippet
Is that GNU_MP code snippet useful?
- It's not all that readable, so it doesn't really add to the article content (except in length).
- It's also debatable whether it is correct. The catch is that m is presumed to fit in an
unsigned long, since the array of baby-step indices is an array of such, but m is computed as the square root of a bignum, which can be a lot larger. One could make an argument that there is an implicit assumption that the code is not to be used for input that would anyway take "forever" to process, but then the choice of using multiple-precision arithmetic becomes suspect, because all numbers should fit comfortably in an integer with just twice the number of bits as an
unsigned long(i.e., an
unsigned long long, at least under some compilers).
- Finally, the table design and lookup mechanism become troublesome asymptotically, if one imagines that the
unsigned longbug is fixed. Binary search in a table with m elements requires comparisons, but those comparisons need to examine at least bits to distinguish elements, so one would expect a time complexity of for just one table lookup. The bitlength of the group elements is , so any fast algorithm for bignum arithmetic (e.g. the Karatsuba algorithm at is asymptotically dominated by the subsequent lookup step. That's pretty silly. 18.104.22.168 (talk) 12:24, 23 May 2017 (UTC)