Funktionen:
| f(x) | x² | falls x ≡ 0 mod 3 | |
| x&alpha | falls x ≡ 1 mod 3 | ||
| x&beta | falls x ≡ 2 mod 3 | ||
| g(x,n) | 2n | falls x ≡ 0 mod 3 | |
| n+1 | falls x ≡ 1 mod 3 | ||
| n | falls x ≡ 2 mod 3 | ||
| h(x,n) | 2n | falls x ≡ 0 mod 3 | |
| n | falls x ≡ 1 mod 3 | ||
| n+1 | falls x ≡ 2 mod 3 | ||
Ablauf des Algorithmus:
| 1. | Initialisierung a0=0, b0=0, x0=1, i=1 | |
| 2. | xi:= f(xi-1) | |
| ai:= g(xi-1,ai-1) | ||
| bi:= h(xi-1,bi-1) | ||
| 3. | x2i:= f(f(x2i-2) | |
| a2i:= g(f(x2i-2,g(x2i-2,a2i-2)) | ||
| b2i:= h(f(x2i-2,h(x2i-2,b2i-2)) | ||
| 4. | Falls xi = x2i | |
| 1. Berechne r = bi - b2i | ||
| 2. Falls r = 0 -> Abbruch! | ||
| 3. x = (a - A) / (B - b) mod p-1 | ||
| 4. return x | ||
| 5. | Falls xi ≠ x2i dann i = i + 1 und gehe zu Schritt 2 | |
|
|
2.5.3 Pohlig–Hellman–Algorithmus | |