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
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: