Index-Calculus-Algorithmus
# Index-Calculus-Algorithmus

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

## Vorgehensweise

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

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}^{n_{t}}p_{i}^{\lambda _{i}}$

Wenn eine entsprechende Darstellung gefunden wurde, kann eine lineare Kongruenz gebildet werden. $a\equiv \sum \limits _{i=1}^{n_{t}}\lambda _{i}\log _{\alpha }p_{i}\mod n$

Wenn eine genügend große Anzahl ($n_{t}>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\leq i\leq t$ besitzt.

### 2. Schritt

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}^{n_{t}}p_{i}^{b_{i}}$ Es gilt: $\log _{\alpha }\beta =\sum \limits _{i=1}^{n_{t}}b_{i}\log _{\alpha }p_{i}-s\mod n$

