Index-Calculus-Algorithmus

Der Index-Calculus-Algorithmus ist ein Algorithmus zur Berechnung des diskreten Logarithmus. <math>x = \log_{\alpha} \beta</math>

Vorgehensweise

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

1. Schritt

Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:
<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}} </math>

Wenn eine entsprechende Darstellung gefunden wurde, kann eine lineare Kongruenz gebildet werden.
<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>

Wenn eine genügend große Anzahl (<math>\ge t</math>) an Relationen gefunden wurde, kann erwartet werden, dass das zugehörige lineare Gleichungssystem eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.

2. Schritt

In diesem Schritt werden die individuellen Logarithmen in <math>G</math> berechnet. <math>\beta \in G</math> ist gegeben. Es werden solange Zufallszahlen <math>s</math> gewählt, bis <math>\alpha^s \beta</math> sich als Produkt von Elementen aus <math>S</math> schreiben lässt:
<math>\alpha^s \beta = \prod \limits_{i=1}^{n_t} p_{i}^{b_i}</math>
Es gilt:
<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \mod n</math>