Baby-step giant-step

Baby-step giant-step

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. 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 G of order n, a generator alpha of the group and a group element eta, the problem is to find an integer x such that: alpha^x = eta,.The baby-step giant-step algorithm is based on rewriting x as x = im + j, with m = lceil sqrt{n} ceil and 0 leq i < m and 0 leq j < m. Therefore, we have::eta(alpha^{-m})^i=alpha^j,.

The algorithm precomputes alpha^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 alpha^j.

The algorithm

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

Output: A value "x" satisfying alpha^{x}=eta.

# "m" ← Ceiling(√"n")
# For all "j" where 0 ≤ "j" &lt; "m":
## Compute α"j" and store the pair ("j", α"j") in a table. (See section "In practice")
# Compute α−"m".
# γ ← β.
# For "i" = 0 to ("m" − 1):
## Check to see if γ is the second component (α"j") of any pair in the table.
## If so, return "im" + "j".
## 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. 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.

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

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.
* The algorithm requires 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 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.
* The algorithm was originally developed by Daniel Shanks.

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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Baby-step giant-step — En théorie des groupes, une branche des mathématiques, l algorithme baby step giant step est une série d étapes bien définies pour calculer le logarithme discret. Le problème du logarithme discret, sur lequel se basent la plupart des… …   Wikipédia en Français

  • baby step — (in the game of giant steps) the shortest step permitted a player, executed by placing the heel of one foot against the toe of the other and drawing the back foot up to the front foot. Cf. umbrella step. * * * …   Universalium

  • baby step — (in the game of giant steps) the shortest step permitted a player, executed by placing the heel of one foot against the toe of the other and drawing the back foot up to the front foot. Cf. umbrella step …   Useful english dictionary

  • giant steps — 1. a children s game in which a leader calls upon individual players to advance toward him or her in a given number and variety of steps, the object being for one person to tag the leader and for all of them to run back to the starting line… …   Universalium

  • giant steps — 1. a children s game in which a leader calls upon individual players to advance toward him or her in a given number and variety of steps, the object being for one person to tag the leader and for all of them to run back to the starting line… …   Useful english dictionary

  • Giant's Causeway — For other uses, see Giant s Causeway (disambiguation). Coordinates: 55°14′27″N 6°30′42″W / 55.24083°N 6.51167°W / 55.2 …   Wikipedia

  • step — {{Roman}}I.{{/Roman}} noun 1 in walking, running, etc. ADJECTIVE ▪ large, small ▪ heavy, light ▪ quick, slow ▪ hesitant …   Collocations dictionary

  • umbrella step — (in the game of giant steps) a step executed by extending one foot forward and whirling on the heel. Cf. baby step. * * * …   Universalium

  • umbrella step — (in the game of giant steps) a step executed by extending one foot forward and whirling on the heel. Cf. baby step …   Useful english dictionary

  • Counting points on elliptic curves — An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”