Index-Calculus-Algorithmus

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

Vorgehensweise

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

1. Schritt

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

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

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

2. Schritt

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