Pohlig–Hellman algorithm

Steps of the Pohlig-Hellman algorithm.

In number theory, the Pohlig–Hellman algorithm sometimes credited as the Silver–Pohlig–Hellman algorithm^[1] is a special-purpose algorithm for computing discrete logarithms in a multiplicative group whose order is a smooth integer.

The algorithm was discovered by Roland Silver, but first published by Stephen Pohlig and Martin Hellman (independent of Silver).

We will explain the algorithm as it applies to the group Z^*_p consisting of all the elements of Z_p which are coprime to p, and leave it to the advanced reader to extend the algorithm to other groups by using Lagrange's theorem.

Input Integers p, g, e.

Output An Integer x, such that e ≡ g^x (mod p) (if one exists).

Determine the prime factorization of the order of the group :
$\varphi (p)=p_{1}\cdot p_{2}\cdots p_{n}$ (All the p_i are considered small since the group order is smooth.)
From the Chinese remainder theorem it will be sufficient to determine the values of x modulo each prime power dividing the group order. Suppose for illustration that p₁ divides this order but p₁² does not. Then we need to determine x mod p₁, that is, we need to know the ending coefficient b₁ in the base-p₁ expansion of x, i.e. in the expansion x = a₁ p₁ + b₁. We can find the value of b₁ by examining all the possible values between 0 and p₁-1. (We may also use a faster algorithm such as baby-step giant-step when the order of the group is prime.^[2]) The key behind the examination is that:
${\begin{aligned}e^{{\varphi (p)/p_{1}}}&\equiv (g^{x})^{{\varphi (p)/p_{1}}}{\pmod {p}}\\&\equiv (g^{{\varphi (p)}})^{{a_{1}}}g^{{b_{1}\varphi (p)/p_{1}}}{\pmod {p}}\\&\equiv (g^{{\varphi (p)/p_{1}}})^{{b_{1}}}{\pmod {p}}\end{aligned}}$
(using Euler's theorem). With everything else now known, we may try each value of b₁ to see which makes the equation be true. If $g^{{\varphi (p)/p_{1}}}\not \equiv 1{\pmod {p}}$ , then there is exactly one b₁, and that b₁ is the value of x modulo p₁. (An exception arises if $g^{{\varphi (p)/p_{1}}}\equiv 1{\pmod {p}}$ since then the order of g is less than φ(p). The conclusion in this case depends on the value of $e^{{\varphi (p)/p_{1}}}\mod p$ on the left: if this quantity is not 1, then no solution x exists; if instead this quantity is also equal to 1, there will be more than one solution for x less than φ(p), but since we are attempting to return only one solution x, we may use b₁=0.)
The same operation is now performed for p₂ through p_n.
A minor modification is needed where a prime number is repeated. Suppose we are seeing p_i for the (k + 1)st time. Then we already know c_i in the equation x = a_i p_i^k+1 + b_i p_i^k + c_i, and we find either b_i or c_i the same way as before, depending on whether $g^{{\varphi (p)/p_{i}}}\equiv 1{\pmod {p}}$ .
With all the b_i known, we have enough simultaneous congruences to determine x using the Chinese remainder theorem.

Complexity

The worst-case time complexity of the Pohlig–Hellman algorithm is $O({\sqrt n})$ for a group of order n, but it is more efficient if the order is smooth. Specifically, if $\prod _{i}p_{i}^{{e_{i}}}$ is the prime factorization of n, then the complexity can be stated as $O\left(\sum _{i}{e_{i}(\log n+{\sqrt p}_{i})}\right)$ .^[3]

Notes

References

Mollin, Richard (2006-09-18). An Introduction To Cryptography (2nd ed.). Chapman and Hall/CRC. p. 344. ISBN 978-1-58488-618-1.
S. Pohlig and M. Hellman (1978). "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance" (PDF). IEEE Transactions on Information Theory (24): 106–110.
Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). "Number-Theoretic Reference Problems" (PDF). Handbook of Applied Cryptography. CRC Press. pp. 107–109. ISBN 0-8493-8523-7.

Number-theoretic algorithms

Primality tests	AKS test APR test Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin

Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization

Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's

Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's

Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve

Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's

Modular square root	Cipolla Pocklington's Tonelli–Shanks

Other algorithms	Chakravala Cornacchia LLL Integer square root Modular exponentiation Schoof's

Italics indicate that algorithm is for numbers of special forms

This article is issued from Wikipedia - version of the 9/26/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.