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.

Vorgehensweise[Bearbeiten | Quelltext bearbeiten]

Es sei eine endliche zyklische Gruppe der Ordnung , die durch erzeugt wird.
Es sei (die Faktorbasis) eine Untermenge von mit der Eigenschaft, dass ein bedeutender Teil der Gruppenelemente sich als Produkt der Elemente in schreiben lässt.

1. Schritt[Bearbeiten | Quelltext bearbeiten]

Es wird eine Zufallszahl gewählt und versucht als Produkt der Elemente aus der Faktorbasis zu schreiben:

Wenn eine entsprechende Darstellung gefunden wurde, kann eine lineare Kongruenz gebildet werden.

Wenn eine genügend große Anzahl () an Relationen gefunden wurde, kann erwartet werden, dass das zugehörige lineare Gleichungssystem eine eindeutige Lösung für die Unbekannten mit besitzt.

2. Schritt[Bearbeiten | Quelltext bearbeiten]

In diesem Schritt werden die individuellen Logarithmen in berechnet. ist gegeben. Es werden solange Zufallszahlen gewählt, bis sich als Produkt von Elementen aus schreiben lässt:

Es gilt: