Index-Calculus-Algorithmus

Der Index-Calculus-Algorithmus ist ein Algorithmus zur Berechnung des diskreten Logarithmus. x = log _αβ

Vorgehensweise

Es sei G eine endliche zyklische Gruppe der Ordnung n, die durch α erzeugt wird.
Es sei S = p₁,p₂,...,p_t(die Faktorbasis) eine Untermenge von G mit der Eigenschaft, dass ein bedeutender Teil der Gruppenelemente sich als Produkt der Elemente S schreiben lässt.

1. Schritt

Es wird eine Zufallszahl a gewählt und versucht α^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 _αp_i mit $1 \le i \le t$ besitzt.

2. Schritt

In diesem Schritt werden die individuelle Logarithmen in G berechnet. $\beta \in G$ ist gegeben. Es werden solange Zufallszahlen s gewählt, bis α^sβ 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$