Diskreter Logarithmus

$x$ heißt diskreter Logarithmus von $a$ zur Basis $g$ modulo $p$.

$x$ ist natürlich nur modulo der Ordnung von $g$ bestimmt, deswegen können wir $x$ auch direkt auf $0\leq x\leq \operatorname{ord}_p(g)-1$ beschränken.

Wenn $p$ eine Primzahl ist, dann ist die Gleichung genau dann lösbar, wenn

$g^x$ können wir sehr schnell mit der Square-And-Multiply-Methode berechnen. Wie kommen wir aber auf das richtige $x$ ?

Naive Berechnung