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 _{i=1}^t{p}_i^{{\lambda }_i}$

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

Wenn eine genügend große Anzahl ($\ge 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\le i\le 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 _{i=1}^{n_t}{p}_i^{b_i}$
Es gilt:
${\log }_{\alpha }\beta =\sum _{i=1}^t{b}_i{\log }_{\alpha }{p}_i-smodn$