Quelltext der Seite Index-Calculus-Algorithmus

Der '''Index-Calculus-Algorithmus''' ist ein [[Algorithmus]] zur Berechnung des [[diskreter Logarithmus|diskreten Logarithmus]].
<math>x = \log_{\alpha} \beta</math>

== Vorgehensweise ==
Es sei <math>G</math> eine endliche [[zyklische Gruppe]] der [[Gruppenordnung|Ordnung]] <math>n</math>, die durch <math>\alpha</math> erzeugt wird.<br>
Es sei <math>S= \{p_{1},p_{2},...,p_{t}\}</math> (die ''Faktorbasis'') eine [[Untermenge]] von <math>G</math> mit der Eigenschaft, dass ein bedeutender Teil der Gruppenelemente sich als Produkt der Elemente in <math>S</math> schreiben lässt.

=== 1. Schritt ===
Es wird eine Zufallszahl <math>a</math> gewählt und versucht <math>\alpha^{a}</math> als Produkt der Elemente aus der Faktorbasis <math>S</math> zu schreiben:<br>
<math>\alpha^{a} = \prod \limits_{i=1}^{t} p_{i}^{\lambda_{i}} </math>

Wenn eine entsprechende Darstellung gefunden wurde, kann eine [[Kongruenz (Zahlentheorie)|lineare Kongruenz]] gebildet werden.<br>
<math>a \equiv \sum \limits_{i=1}^{t}\lambda_i \log_{\alpha} p_i \mod n</math>

Wenn eine genügend große Anzahl (<math>\ge t</math>) an [[Relation (Mathematik)|Relationen]] gefunden wurde, kann erwartet werden, dass das zugehörige [[Lineares Gleichungssystem|lineare Gleichungssystem]] eine eindeutige Lösung für die Unbekannten <math>\log_\alpha p_i</math> mit <math>1 \le i \le t</math> besitzt.

=== 2. Schritt ===
In diesem Schritt werden die individuellen Logarithmen in <math>G</math> berechnet.
<math>\beta \in G</math> ist gegeben.
Es werden solange Zufallszahlen <math>s</math> gewählt, bis <math>\alpha^s \beta</math> sich als Produkt von Elementen aus <math>S</math> schreiben lässt:<br>
<math>\alpha^s \beta = \prod \limits_{i=1}^{n_t} p_{i}^{b_i}</math><br>
Es gilt:<br>
<math>\log_{\alpha} \beta = \sum \limits_{i=1}^{t} b_i \log_{\alpha} p_i - s \mod n</math>

[[Kategorie:Zahlentheoretischer Algorithmus]]