|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? 22.214.171.124 (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. 126.96.36.199 (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 188.8.131.52 (talk) 11:59, 22 July 2010 (UTC)