Index calculus algorithm

The index - calculus algorithm is an algorithm for computing the discrete logarithm.

Method

It is a finite cyclic group of order that is generated by. Let ( the factor base ) a subset of with the property that a significant part of the group elements can be written as a product of elements in.

Step 1

It is chosen a random number and tried to write as a product of the elements of the factor base:

If a corresponding representation was found, a linear congruence can be formed.

If a sufficiently large number () was found to ratios, it can be expected that the corresponding linear equations has a unique solution for the unknown with.

Step 2

In this step, the individual logarithms calculated. is given. Images will be chosen random numbers until can be written as a product of elements from: The following applies:

• Theoretical number algorithm