Index-Calculus-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Vorgehensweise[Bearbeiten]

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[Bearbeiten]

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 \le i \le t besitzt.

2. Schritt[Bearbeiten]

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