Index-Calculus-Algorithmus

Diskreter Logarithmus berechnen

Der Index-Calculus-Algorithmus ist ein Algorithmus zur Berechnung des diskreten Logarithmus.

VorgehensweiseBearbeiten

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. SchrittBearbeiten

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. SchrittBearbeiten

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: