In group theory, a branch of mathematics, the baby-step giant-step algorithm is a series of well-defined steps to compute the discrete logarithm. Group theory is a mathematical discipline the part of Abstract algebra that studies the Algebraic structures known as groups. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation In Mathematics, specifically in Abstract algebra and its applications discrete logarithms are group-theoretic analogues of ordinary Logarithms The discrete log problem is of fundamental importance to the area of public key cryptography. Public-key cryptography, also known as asymmetric cryptography, is a form of Cryptography in which the key used to encrypt a message differs from the key 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.

Contents 1 Theory 2 The algorithm 3 In practice 4 Notes 5 References

Theory

The algorithm is based on a space-time tradeoff. In Computer science, a space-time or time-memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution or It is a fairly simple modification of trial multiplication, the naive method of finding discrete logarithms.

Given a cyclic group G of order n, a generator α of the group and a group element β, the problem is to find an integer x such that

The baby-step giant-step algorithm is based on rewriting x as x = im + j, with and and . In Group theory, a cyclic group or monogenous group is a group that can be generated by a single element in the sense that the group has an In Abstract algebra, a generating set of a group G is a Subset S such that every element of G can be expressed as the Therefore, we have:

The algorithm precomputes α^j for several values of j. Then it fixes an m and tries values of i in the left-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 j, using the precomputed values of α^j.

The algorithm

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

Output: A value x satisfying α^x = β.

1. m ← Ceiling(√n)
2. For all j where 0 ≤ j < m:
   1. Compute α^j and store the pair (j, α^j) in a table. (See section "In practice")
3. Compute α^−m.
4. γ ← β.
5. For i = 0 to (m − 1):
   1. Check to see if γ is the second component (α^j) of any pair in the table.
   2. If so, return im + j.
   3. If not, γ ← γ • α^−m.

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. In Computer science, a hash table, or a hash map, is a Data structure that associates keys with values. 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 O(1) time (constant time), this does not slow down the overall baby-step giant-step algorithm. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments

The running time of the algorithm is O(√n). The space complexity is the same.

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 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. In mathematics the Pohlig–Hellman algorithm is an Algorithm for the computation of Discrete logarithms in a Multiplicative group whose order is a
• The algorithm requires O(m) memory. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments 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 O(n/m). In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments 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. Pollard's rho algorithm for logarithms is an algorithm for solving the Discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer

References

• H. Cohen, A course in computational algebraic number theory, Springer, 1996.
• 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.
• A. V. Sutherland, Order computations in generic groups, PhD thesis, M. I. T. , 2007, http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf.
• D. C. Terr, A modification of Shanks’ baby-step giant-step algorithm, Mathematics of Computation 69 (2000), 767–773.

---

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic