Pohlig-Hellman algorithm - AbsoluteAstronomy.com

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, the Pohlig–Hellman algorithm sometimes credited as the Silver–Pohlig–Hellman algorithm is a special-purpose algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

for computing discrete logarithm

Discrete logarithm

In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

s in a multiplicative group

Multiplicative group

In mathematics and group theory the term multiplicative group refers to one of the following concepts, depending on the context*any group \scriptstyle\mathfrak \,\! whose binary operation is written in multiplicative notation ,*the underlying group under multiplication of the invertible elements of...

whose order is a smooth integer.

The algorithm was discovered by Roland Silver, but first published by Stephen Pohlig

Stephen Pohlig

Stephen Pohlig is an electrical engineer currently working at MIT Lincoln Laboratory. As a graduate student of Martin Hellman's at Stanford University in the mid-1970's, he helped develop the Pohlig–Hellman exponentiation cipher and the Pohlig–Hellman algorithm for computing discrete...

and Martin Hellman

Martin Hellman

Martin Edward Hellman is an American cryptologist, and is best known for his invention of public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle...

(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

Coprime

In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...

to p, and leave it to the advanced reader to extend the algorithm to other groups by using Lagrange's theorem

Lagrange's theorem (group theory)

Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

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 (the totient in this case) :
(All the p_i are considered small since the group order is smooth.)
From the Chinese remainder theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...

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
Baby-step giant-step
In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm computing the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography...

when the order of the group is prime.) The key behind the examination is that:

(using Euler's theorem). With everything else now known, we may try each value of b₁ to see which makes the equation be true; precisely one will work, and that b₁ is the value of x modulo p₁. (An exception arises if since then the order of g is less than φ(p). The conclusion in this case depends on the value of 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.)
1. 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 b_i the same way as before.
2. With all the b_i known, we have enough simultaneous congruence
  Congruence relation
  In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
  
  s to determine x using the Chinese remainder theorem
  Chinese remainder theorem
  The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
  
  .
Complexity
The worst-case time complexity of the Pohlig–Hellman algorithm is for a group of order n, but it is more efficient if the order is smooth. Specifically, if is the prime factorization of n, then the complexity can be stated as
.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Complexity