 Pohlig-Hellman algorithm

Algorithm 3.63 for computing logarithms takes advantage of the factorization of the order n of the group G. Let n= pl p£ ■ ■ ■ p%T be the prime factorization of n. If x = loga /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 + - ■ ■+lei-ipeii~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 = alo+ll4+'"+lJ-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 = loga (3.

• 1. Find the prime factorization of n: n = • ■per’, where e, > 1.
• 2. For i from 1 to r do the following:
• 0Compute Xi = Iq + hpi + • • ■ + lei-iPi'~ , where x, = x mod pl)
• 2.1 (Simplify the notation) Set q<—p, and ef—e,.
• 2.2 Set —1 and /_if—0.
• 2.3 Compute cH-an/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 + • • • + le—qe *.
• 3. Use Gauss’s algorithm (Algorithm 2.121) to compute the integer x, 0 < x < n - 1, such that x = Xi (mod p(f) for 1 < г < 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 Z251 of order n = 250. Consider (3 = 210. Then x = log71 210 is computed as follows.
• 1. The prime factorization of n is 250 = 2 • 53.
• 2. (a) (Compute x = x mod 2)

Compute a = anG mod p = 250 and (3 = (3nG mod p = 250. Then x = bg25o 250 = !•

(b) (Compute = x mod 53 = lo + Zi5 + /252)

i. Compute a = an/5 mod p = 20.

ii. Compute 7 = 1 and (3 = (dy-1)"/5 mod p = 149. Using exhaustive search,5 compute Iq = log20 149 = 2.

iii. Compute 7 = 702 mod p = 21 and (3 = (/З7-1 )n/23 mod p = 113. Using exhaustive search, compute /1 = log20 113 = 4.

iv. Compute 7 = 7a4'5 mod p = 115 and (3 = (/З7 ^(p-1)/125 mod p = 149. Using exhaustive search, compute /2 = log20 1 49 = 2.

Hence, X2 = 2 + 4 • 5 + 2 • 52 = 72.

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

x = log71 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 = 24 • 1047298 • 2247378 • 3503774. 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).