# Pohlig-Hellman algorithm

Algorithm 3.63 for computing logarithms takes advantage of the factorization of the order *n *of the group *G.* Let *n= p ^{l} p£ ■ ■ ■ p%^{T}* be the prime factorization of

*n.*If

*x =*log

_{a}

*/3*, then the approach is to determine ж,- =

*x*mod

*pf*fori <

*i < r,*and then use Gauss’s algorithm (Algorithm 2.121) to recover

*x*mod

*n.*Each integer

*x,*is determined by computing the digits

*lo,h, ■ ■ ■ , let-i*in turnofits^-ary representation:

*xt = lo + lipi + - ■ ■+l*

_{ei}-ip^{e}i

^{i}~

^{1}, where 0 <

*lj < p, -*1.

To see that the output of Algorithm 3.63 is correct, observe first that in step 2.3 the order of a is *q.* Next, at iteration *j* of step 2.4,7 = * _{a}^{lo+ll4+}'"^{+l}J-^{1} '.* Hence,

the last equality being true because *a* has order *q.* Hence, logjj- *fj* is indeed equal to *lj.*

3.63 Algorithm Pohlig-Hellman algorithm for computing discrete logarithms

INPUT: a generator a of a cyclic group *G* of order *n,* and an element *(3 e G.*

OUTPUT: the discrete logarithm *x* = log_{a} *(3.*

- 1. Find the prime factorization of
*n: n = • ■*■*p*, where e, > 1.^{e}r’ - 2. For
*i*from 1 to*r*do the following: - 0
*Compute Xi = Iq + hpi*+ • • ■ +*l*=_{ei}-iPi'~ , where x,*x*mod*p*^{l}) - 2.1 (
*Simplify the notation)*Set*q<—p,*and ef—e,. - 2.2 Set —1 and /_if—0.
- 2.3 Compute
*cH-a*^{n}/^{q}. - 2.4 (
*Compute the f)*For*j*from 0 to*e -*1 do the following:

Compute ^{1} and *.*

Compute *lj<-* log*^(3* (e.g., using Algoritlmi 3.56; see Note 3.67(iii)).

- 2.5 Set —Iq +
*lq*+ • • • +*l**._{e}—q^{e} - 3. Use Gauss’s algorithm (Algorithm 2.121) to compute the integer x, 0 < x < n - 1, such that
*x = Xi*(mod*p*) for 1 < г <^{(}f*r.* - 4. Retum(:c).

Example 3.64 illustrates Algorithm 3.63 with artificially small parameters.

- 3.64 Example (
*Pohlig-Helhnan algorithm for logarithms in*Z^) Let*p =*251. The element a = 71 is a generator of Z2_{51}of order*n =*250. Consider*(3 =*210. Then*x =*log_{71}210 is computed as follows. - 1. The prime factorization of
*n*is 250 = 2 • 5^{3}. - 2. (a) (Compute
*x = x*mod 2)

Compute *a = a ^{n}G* mod

*p =*250 and

*(3*=

*(3*mod

^{n}G*p =*250. Then

*x*= bg

_{25}o

^{250}= !•

(b) (Compute = *x* mod 5^{3} = *lo* + Zi5 + /_{2}5^{2})

i. Compute *a = a ^{n}/^{5}* mod

*p =*20.

ii. Compute 7 = 1 and *(3* = (dy^{-1})"/^{5} mod *p* = 149. Using exhaustive search,^{5} compute Iq = log_{20} 149 = 2.

iii. Compute 7 = 70^{2} mod *p **=* 21 and *(3* = (/З7^{-1} )^{n}/^{23} mod *p **=* 113. Using exhaustive search, compute /1 = log_{20} 113 = 4.

iv. Compute 7 = 7a^{4}'^{5} mod *p =* 115 and *(3 =* (/З7 ^(p^{-1})/^{125} mod *p* = 149. Using exhaustive search, compute /_{2} = log_{20} 1 49 = 2.

Hence, *X**2** =* 2 + 4 • 5 + 2 • 5^{2} = 72.

3. Finally, solve the pair of congruences *x =* 1 (mod 2), *x =* 72 (mod 125) to get

*x* = log_{71} 210 = 197. □

- 3.65 Fact Given the factorization of n, the running time of the Pohlig-Hellman algorithm (Algoritlmi 3.63) is 0(Xa
_{=1}^{e}*(lg^{n}+ v/p7)) group multiplications. - 3.66 Note (
*effectiveness of Pohlig-Hellman)*Fact 3.65 implies that the Pohlig-Helhnan algorithm is efficient only if each prime divisor*p,*of*n*is relatively small; that is, if*n*is a smooth

Exhaustive search is preferable to Algorithm 3.56 when the group is very small (here the order of a is 5).

integer (Definition 3.13). An example of a group in which the PohUg-Hellman algorithm is effective follows. Consider the multiplicative group Z* where *p* is the 107-digit prime:

The order of Z* is n = *p* - 1 = 2^{4} • 104729^{8} • 224737^{8} • 350377^{4}. Since the largest prune divisor of *p -* 1 is only 350377, it is relatively easy to compute logarithms in this group using the Pohlig-Hellman algorithm.

- 3.67 Note (
*miscellaneous*) - (i) If
*n*is a prune, then Algorithm 3.63 (Pohlig-Hellman) is the same as baby-step giant- step (Algorithm 3.56). - (ii) In step 1 of Algorithm 3.63, a factoring algorithm which finds small factors first (e.g., Algorithm 3.9) should be employed; if the order
*n*is not a smooth integer, then Algorithm 3.63 is inefficient anyway. - (iii) The storage required for Algorithm 3.56 in step 2.4 can be eliminated by using instead Pollard’s rho algorithm (Algorithm 3.60).