Babystep-Giantstep algorithm

from Wikipedia, the free encyclopedia

The babystep-giantstep algorithm (also called Shanks' discrete logarithm algorithm ) calculates the discrete logarithm of an element of a cyclic group . Although the algorithm is superior to naive trying out all possibilities in terms of runtime, it is still not practicable for very large groups. The algorithm comes from Daniel Shanks .

theory

Find the discrete logarithm with a finite cyclic group of the order and a group element.

By dividing by the rest can be at a fixed chosen a unique representation to find. This is often chosen (see Landau symbols ) in order to keep the possible number range of and similarly large. By reshaping, this representation results in the property on which the algorithm is based .

The algorithm looks for a pair that fulfills this characteristic and first creates a table of the “baby steps” . Then the "giant steps" are successively calculated for the growing ones and checked for equality with a value in the table. If there is such a collision, this is the pair searched for and the logarithm is output.

With access times to individual elements of the table of - in the case of suitably fast data structures such as hash tables , this corresponds to - the algorithm has a runtime of with memory requirements .

algorithm

Input: finite cyclic group , producer , group element

Edition: with

  • Calculate , with the rounding function .
  • For everyone : calculate and save in a table.
  • For everyone : calculate and search for it in the second column of the table. If found, output .

Because of this, the group element can easily be calculated in the last step from that of the previous iteration.

example

Because a primitive root is modulo , we have . So be the prime remainder class group with producer . We want to calculate the discrete logarithm of the base , i.e. the solution of .

  • The group order is found to be , as a prime number (this is the Euler φ function ). So is .
  • For one calculates the pairs and saves them in a table:
0 1 2 3 4th 5
1 11 5 26th 25th 14th
  • It is . Calculate for the number and terminate as soon as it is found in the second component of the previous table:
0 1 2
3 10 14th

So it is and , so is .