Baby-step giant-step

The baby-step giant-step algorithm computes the discrete logarithm of an element of a cyclic group. The algorithm is indeed superior to the naive trying all possibilities in life, but is still very large groups practically not feasible. The algorithm comes from Daniel Shanks.

Theory

Wanted is the discrete logarithm finite cyclic group of order n and a group element.

By dividing by the rest can be found at a fixed m chosen a unique representation. This is often selected (see Landau symbols) in order to keep the possible numerical range of i and j are similar in size. Rearranging results with this view because the algorithm underlying property.

The algorithm is looking for a pair (i, j), which satisfies this property, and this first creates a table of the " Baby Steps ." Then one calculates for growing i successively the "giant steps" and checks for equality with a value in the table. If such a collision, this is the desired pair and the logarithm is returned.

With access times to individual elements of the table - in the case of suitable fast data structures like a hash table, this corresponds to - the algorithm has a running time of with memory requirements.

Algorithm

Input: finite cyclic group, producer, group element

Edition: with

• Compute
• For all: Compute and store in a table.
• For all: Compute and look for it in the second column of the table. If found, give out.

Ways can the group element in the last step easily from the directions of the previous iteration.

Example

Because a primitive root modulo applies. So be the residue class group with generators. We want to compute the discrete logarithm of to the base.

• The group order is given by, there is a prime number (this is Euler's φ - function). Thus is.
• For calculating the pairs and stores them in a table:

• It is. Calculating the number and terminated as soon as it was found in the second component of the previous table:

• Theoretical number algorithm