Index Calculus Algorithm

The Index Calculus Algorithm is an algorithm for calculating the discrete logarithm . ${\displaystyle x=\log _{\alpha }\beta }$

method

It is a finite cyclic group of order represented by is generated. Let (the factor base ) be a subset of with the property that a significant part of the group elements can be written as the product of the elements in . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \alpha }$
${\displaystyle S=\{p_{1},p_{2},...,p_{t}\}}$ ${\displaystyle G}$ ${\displaystyle S}$

Step 1

A random number is chosen and an attempt is made to write as the product of the elements from the factor base : ${\displaystyle a}$ ${\displaystyle \alpha ^{a}}$ ${\displaystyle S}$
${\displaystyle \alpha ^{a}=\prod \limits _{i=1}^{t}p_{i}^{\lambda _{i}}\mod n}$

If a corresponding representation has been found, a linear congruence can be formed.
${\displaystyle a\equiv \sum \limits _{i=1}^{t}\lambda _{i}\log _{\alpha }p_{i}\mod (n-1)}$

If a sufficient number ( ) on relations was found, it can be expected that the associated system of linear equations has a unique solution for the unknowns with has. ${\displaystyle >t}$ ${\displaystyle \log _{\alpha }p_{i}}$ ${\displaystyle 1\leq i\leq t}$

2nd step

In this step the individual logarithms are calculated in. is given. Random numbers are chosen until the product of elements can be written: The following applies: ${\displaystyle G}$ ${\displaystyle \beta \in G}$ ${\displaystyle s}$ ${\displaystyle \alpha ^{s}\beta }$ ${\displaystyle S}$
${\displaystyle \alpha ^{s}\beta =\prod \limits _{i=1}^{t}p_{i}^{b_{i}}}$

${\displaystyle \log _{\alpha }\beta =\sum \limits _{i=1}^{t}b_{i}\log _{\alpha }p_{i}-s\mod n}$