Information About

Baby-step Giant-step
  CATEGORIES ABOUT BABY-STEP GIANT-STEP
   
group theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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 are 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
: \alpha^x = \beta\,.
where α, β and ''n'' are given. The baby-step giant-step algorithm is based on rewriting ''x'' as ''x'' = ''im'' + ''j'', with ''m'' constant and 0 ≤ ''i'', ''j'' < ''m''. Therefore, we have:
:\beta(\alpha^{-m})^i=\alpha^j\,.

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 \alpha^{x}=\beta.

# ''m'' ← Ceiling(√n)
# For all ''j'' where 0 ≤ ''j'' < ''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 is:
:O(\sqrt{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.

  • 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.



REFERENCE

D. Shanks. Class number, a theory of factorization and genera. In Proc. Symp. Pure Math. 20, pages 415--440. AMS, Providence, R.I., 1971.