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.

References[edit]

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[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? 72.93.101.152 (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 86.64.192.254 (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. 62.203.32.82 (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 218.65.102.178 (talk) 11:59, 22 July 2010 (UTC) 

GNU_MP code snippet[edit]

Is that GNU_MP code snippet useful?

  1. It's not all that readable, so it doesn't really add to the article content (except in length).
  2. 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).
  3. Finally, the table design and lookup mechanism become troublesome asymptotically, if one imagines that the unsigned long bug 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. 130.243.68.122 (talk) 12:24, 23 May 2017 (UTC)