Index-Calculus-Algorithmus

Der Index-Calculus-Algorithmus ist ein Algorithmus zur Berechnung des diskreten Logarithmus. $x=\log _{\alpha }\beta$

Vorgehensweise

Es sei $G$ eine endliche zyklische Gruppe der Ordnung $n$, die durch $\alpha$ erzeugt wird.
Es sei $S=\{p_{1},p_{2},...,p_{t}\}$ (die Faktorbasis) eine Untermenge von $G$ mit der Eigenschaft, dass ein bedeutender Teil der Gruppenelemente sich als Produkt der Elemente in $S$ schreiben lässt.

1. Schritt

Es wird eine Zufallszahl $a$ gewählt und versucht $\alpha ^{a}$ als Produkt der Elemente aus der Faktorbasis $S$ zu schreiben:
$\alpha ^{a}=\prod \limits _{i=1}^{t}p_{i}^{\lambda _{i}}$

Wenn eine entsprechende Darstellung gefunden wurde, kann eine lineare Kongruenz gebildet werden.
$a\equiv \sum \limits _{i=1}^{t}\lambda _{i}\log _{\alpha }p_{i}\mod n$

Wenn eine genügend große Anzahl ($>t$) an Relationen gefunden wurde, kann erwartet werden, dass das zugehörige lineare Gleichungssystem eine eindeutige Lösung für die Unbekannten $\log _{\alpha }p_{i}$ mit $1\leq i\leq t$ besitzt.

2. Schritt

In diesem Schritt werden die individuellen Logarithmen in $G$ berechnet. $\beta \in G$ ist gegeben. Es werden solange Zufallszahlen $s$ gewählt, bis $\alpha ^{s}\beta$ sich als Produkt von Elementen aus $S$ schreiben lässt:
$\alpha ^{s}\beta =\prod \limits _{i=1}^{t}p_{i}^{b_{i}}$
Es gilt:
$\log _{\alpha }\beta =\sum \limits _{i=1}^{t}b_{i}\log _{\alpha }p_{i}-s\mod n$