functions:
| f(x) | x˛ | if x ≡ 0 mod 3 | |
| x&alpha | if x ≡ 1 mod 3 | ||
| x&beta | if x ≡ 2 mod 3 | ||
| g(x,n) | 2n | if x ≡ 0 mod 3 | |
| n+1 | if x ≡ 1 mod 3 | ||
| n | if x ≡ 2 mod 3 | ||
| h(x,n) | 2n | if x ≡ 0 mod 3 | |
| n | if x ≡ 1 mod 3 | ||
| n+1 | if x ≡ 2 mod 3 | ||
steps of the algorithm:
| 1. | initialise 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. | if xi = x2i | |
| 1. calculate r = bi - b2i | ||
| 2. if r = 0 return failure | ||
| 3. x = (a - A) / (B - b) mod p-1 | ||
| 4. return x | ||
| 5. | if xi ≠ x2i then i = i + 1 and go to step 2 | |
|
|
2.5.3 Pohlig–Hellman algorithm | |