Pohlig-Hellman Algorithm

From Notes
Jump to navigation Jump to search

The Pohlig-Hellman algorithm is useful in finding the discrete logarithm Lα of a number and modulus. In other words, we wish to solve the following expression for x.

β≡αx⟺x≡Lα(β)(modp)

We'll use the Lα(β) notation to represent this solution. Given the prime factorization of p−1,

p−1=∏iqiri

We can solve Lα(β)(modqr) for each qiri (in other words, calculate x(modqr) for each factor) and then recombine them using the Chinese remainder theorem to find x. Let's start by finding the base-q expansion of x:

x=d0+d1q+d2q2+…

where each di is an integer digit between 0 and q−1. We can find the digits d0 through dr−1 successively to find x(modqr). Let's multiply both sides of the equation above by p−1q:

x(p−1q)=d0(p−1q)+(p−1)(d1+d2q+d3q2+…)=d0(p−1q)+(p−1)N

Where N is some integer. Let's raise each side of our original problem statement β≡αx(modp) to the same p−1q power:

βp−1q≡(αx)p−1q(modp)≡αx(p−1q)(modp)≡αd0(p−1q)+(p−1)N(modp)≡αd0(p−1q)α(p−1)N(modp)≡αd0(p−1q)(modp)
Note: That last cancellation was by Fermat's little theorem.

Now we just have to try possible values for d0 until the following congruence works out:

βp−1q≡(αp−1q)d0(modp)d0∈{0,1,2,…,q−1}

Now that we know d0, we can find remaining digits (up to dr−1) in succession. Notice by our original problem and our base expansion for x that we have

β≡αx(modp)≡αd0+d1q+d2q2+…(modp)≡αd0αq(d1+d2q+d3q2+…)(modp)βα−d0≡αq(d1+d2q+d3q2+…)(modp)

Now similar to what we did above, we can raise both sides to the p−1qk power (notice k=1 in the first step) for k up to r (as qr is the highest prime power that divides p−1). In this case, we'll take k=2:

(βα−d0)p−1q2≡(αq(d1+d2q+d3q2+…))p−1q2≡αp−1q(d1+d2q+d3q2+…)(modp)≡αd1(p−1q)+(p−1)(d2+d3q+d4q2+…)(modp)≡αd1(p−1q)+(p−1)N(modp)≡αd1(p−1q)α(p−1)N(modp)

Once again, we reduced by Fermat's little theorem, and now we can try values for d1 until we find the one that makes the equivalence work.

(βα−d0)p−1q2≡(αp−1q)d1(modp)d1∈{0,1,2,…,q−1}

Continue this process until we have all base qr digits di for x.

(β∏i=0knownα−diqi)p−1qk≡(αp−1q)dk−1(modp)dk−1∈{1,2,…,q−1}

Now we know x mod qr.

Repeat this process for all prime factors qiri dividing p−1, and then combine them with the Chinese remainder theorem.