Das Kefk Network Wiki befindet sich im Testbetrieb.

Index-Calculus-Algorithmus

Aus Kefk.

Wechseln zu: Navigation, Suche

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 = p1,p2,...,pt(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αpi mit 1 \le i \le t bestitzt.

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

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Index-Calculus-Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Index-Calculus-Algorithmus“
Persönliche Werkzeuge