Talk:Baby-step giant-step

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
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.
Mathematics rating:
B Class
Mid Importance
 Field: Algebra

Who found it?[edit]

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?Insert formula here775

Several references have been added.

I think there is a slight error in the algorithm's description[edit]

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? (talk) 21:04, 3 December 2008 (UTC)

I am not really sure but I think it's correct: in a group we have the property (a-1)n=(an)-1=a-n —Preceding unsigned comment added by (talk) 13:35, 24 July 2009 (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. (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 (talk) 11:59, 22 July 2010 (UTC)