View source for Baby-step giant-step

{{Short description|Algorithm for solving the discrete logarithm problem}}
In [[group theory]], a branch of mathematics, the '''baby-step giant-step''' is a [[Meet-in-the-middle attack|meet-in-the-middle]] [[algorithm]] for computing the [[discrete logarithm]] or [[order (group theory)|order]] of an element in a [[finite group|finite]] [[abelian group]] by [[Daniel Shanks]].<ref>{{citation|author=Daniel Shanks|authorlink=Daniel Shanks|title=Class number, a theory of factorization and genera|work=In Proc. Symp. Pure Math.|volume=20|pages=415–440|publisher=American Mathematical Society|location=Providence, R.I.|year=1971}}</ref> The discrete log problem is of fundamental importance to the area of [[public key cryptography]].

Many of the most commonly used cryptography systems are based on the assumption that the discrete log is extremely difficult to compute; the more difficult it is, the more security it provides a data transfer. One way to increase the difficulty of the discrete log problem is to base the cryptosystem on a larger group.

==Theory==
The algorithm is based on a [[space–time tradeoff]]. It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.

Given a [[cyclic group]] <math>G</math> of order <math>n</math>, a [[Generating set of a group|generator]] <math>\alpha</math> of the group and a group element <math>\beta</math>, the problem is to find an integer <math>x</math> such that
: <math>\alpha^x = \beta\,.</math>

The baby-step giant-step algorithm is based on rewriting <math>x</math>:
:<math>x = im + j</math>
:<math>m = \left\lceil \sqrt{n} \right\rceil </math>
:<math>0 \leq i < m</math>
:<math>0 \leq j < m</math>
Therefore, we have:
: <math>\alpha^x = \beta\,</math>
: <math>\alpha^{im + j} = \beta\,</math>
: <math>\alpha^j = \beta\left(\alpha^{-m}\right)^i\,</math>
The algorithm precomputes <math>\alpha^j</math> for several values of <math>j</math>. Then it fixes an <math>m</math> and tries values of <math>i</math> in the right-hand side of the congruence above, in the manner of trial multiplication. It tests to see if the congruence is satisfied for any value of <math>j</math>, using the precomputed values of <math>\alpha^j</math>.

==The algorithm==
'''Input''': A cyclic group ''G'' of order ''n'', having a generator ''α'' and an element ''β''.

'''Output''': A value ''x'' satisfying <math>\alpha^x = \beta</math>.

# ''m'' ← Ceiling({{sqrt|''n''}})
# For all ''j'' where 0 ≤ ''j'' &lt; ''m'':
## Compute ''α''<sup>''j''</sup> and store the pair (''j'', ''α''<sup>''j''</sup>) in a table. (See {{section link||In practice}})
# Compute ''α''<sup>−''m''</sup>.
# ''γ'' ← ''β''. (set ''γ'' = ''β'')
# For all ''i'' where 0 ≤ ''i'' &lt; ''m'':
## Check to see if γ is the second component (''α''<sup>''j''</sup>) of any pair in the table.
## If so, return ''im'' + ''j''.
## If not, ''γ'' ← ''γ'' • ''α''<sup>−''m''</sup>.

==In practice==
The best way to speed up the baby-step giant-step algorithm is to use an efficient table lookup scheme. The best in this case is a [[hash table]]. The hashing is done on the second component, and to perform the check in step 1 of the main loop, γ is hashed and the resulting memory address checked. Since hash tables can retrieve and add elements in [[Big O notation|<math>O(1)</math>]] time (constant time), this does not slow down the overall baby-step giant-step algorithm.

The space complexity of the algorithm is [[Big O notation|<math>O(\sqrt n)</math>]], while the time complexity of the algorithm is <math> O(\sqrt n) </math>. This running time is better than the [[Big O notation|<math>O(n)</math>]] running time of the naive brute force calculation.

The baby-step giant-step algorithm could be used by an eavesdropper to derive the private key generated in the [[Diffie–Hellman key exchange|Diffie Hellman key exchange]], when the modulus is a prime number that is not too large. If the modulus is not prime, the [[Pohlig–Hellman algorithm]] has a smaller algorithmic complexity, and potentially solves the same problem.<ref>{{citation
 | last1 = Maurer | first1 = Ueli M.
 | last2 = Wolf | first2 = Stefan
 | doi = 10.1023/A:1008302122286
 | issue = 2–3
 | journal = Designs, Codes and Cryptography
 | mr = 1759615
 | pages = 147–171
 | title = The Diffie-Hellman protocol
 | volume = 19
 | year = 2000}}</ref>

== Notes ==
* The baby-step giant-step algorithm is a generic algorithm. It works for every finite cyclic group.
* It is not necessary to know the exact order of the group ''G'' in advance. The algorithm still works if ''n'' is merely an upper bound on the group order.
* Usually the baby-step giant-step algorithm is used for groups whose order is prime. If the order of the group is composite then the [[Pohlig–Hellman algorithm]] is more efficient.
* The algorithm requires [[Big O notation|O]](''m'') memory. It is possible to use less memory by choosing a smaller ''m'' in the first step of the algorithm. Doing so increases the running time, which then is [[Big O notation|O]](''n''/''m''). Alternatively one can use [[Pollard's rho algorithm for logarithms]], which has about the same running time as the baby-step giant-step algorithm, but only a small memory requirement.
* While this algorithm is credited to Daniel Shanks, who published the 1971 paper in which it first appears, a 1994 paper by Nechaev<ref>V. I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm, Mathematical Notes, vol. 55, no. 2 1994 (165-172)</ref> states that it was known to [[Alexander Gelfond|Gelfond]] in 1962.
* There exist optimized versions of the original algorithm, such as using the collision-free truncated lookup tables of <ref>{{cite conference|author=Panagiotis Chatzigiannis, Konstantinos Chalkias and Valeria Nikolaenko|title=Homomorphic decryption in blockchains via compressed discrete-log lookup tables|conference=CBT workshop 2021 (ESORICS)|date=2021-06-30|url=https://eprint.iacr.org/2021/899|access-date=2021-09-07}}</ref> or negation maps and Montgomery's simultaneous modular inversion as proposed in.<ref>{{cite conference|author=Steven D. Galbraith, Ping Wang and Fangguo Zhang|title=Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm|conference=Advances in Mathematics of Communications|date=2016-02-10|url=https://eprint.iacr.org/2015/605|access-date=2021-09-07}}</ref>

==Further reading==
* [[Henri Cohen (number theorist)|H. Cohen]], A course in computational algebraic number theory, Springer, 1996.
* [[Daniel Shanks|D. Shanks]], Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415—440. AMS, Providence, R.I., 1971.
* A. Stein and E. Teske, Optimized baby step-giant step methods, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
* [[Andrew Sutherland (mathematician)|A. V. Sutherland]], [https://math.mit.edu/~drew/sutherland-phd.pdf Order computations in generic groups], PhD thesis, M.I.T., 2007.
* D. C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Mathematics of Computation 69 (2000), 767–773. {{doi|10.1090/S0025-5718-99-01141-2}}

==References==

{{Reflist}}

== External links ==
* [https://github.com/viralpoetry/Baby-step-giant-step Baby step-Giant step – example C source code]

{{Number-theoretic algorithms}}

[[Category:Group theory]]
[[Category:Number theoretic algorithms]]
[[Category:Articles with example C++ code]]