An Example of Pohlig-Hellman with a high power of 2\302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.eduAs an example of Pohlig-Hellman it is worthwhile to look at a prime where p-1 is a high power of a single prime.restart:We will look at exercise 7.5 from the text, letting p = 65537, and looking for the log base 3 of 2.We start with the initial set of.p := 65537;
ifactor(p-1);Since 2 is the only prime factor of p-1 we can show that 3 is a generator of Z/p by showing 3^((p-1)/2)\342\211\2401. Power(3,2^15) mod p;Using the notation of the previous worksheet, alpha=3, beta=2.Log_3(2) = x_0 + 2^1*x_1 + ... + 2^15*x_15.We need a look up table of powers of 3^(2^15).Power(3,0) mod p;
Power(3,2^15) mod p;Now we look at beta^(2^(15-i)) looking for the first component of the exponent that is nonzero.for i from 0 to 15 do
test := Power(2, 2^(15-i)) mod p;
print( i, test):
end do:Thus x_0 = x_1 = ... = x_10 = 0, and x_11 = 1.Compute beta11 = beta*(alpha^(2^11))^(-1) and not thatlog_3(beta11) = 2^12*x_12 + ... + 2^15*x_15.beta11 := 2*(Power(3, 2^16-2^11) mod p) mod p;We now repeat the process, starting with 12 to find other nonzero components of the exponent.for i from 12 to 15 do
test := Power(beta11, 2^(15-i)) mod p;
print( i, test):
end do:Thus x_12 = 1.Now beta12 = beta11 * (alpha^(2^12))^(-1) and Note log_3(b12) = 2^13*x_13 + ... + 2^15*x_15.beta12 := beta11*(Power(3, 2^16-2^12) mod p) mod p;for i from 13 to 15 do
test := Power(beta12, 2^(15-i)) mod p;
print( i, test):
end do:Thus x_13 = 0 and x_14 = 1.Now beta14 = beta12 * (alpha^(2^14))^(-1) and Note log_3(b14) = 2^15*x_15.beta14 := beta12*(Power(3, 2^16-2^14) mod p) mod p;By inspection, x_15 = 1.Thus Log_3(2) = 2^15+2^14+2^12+2^11.As always, we verify the result.log3 := 2^15+2^14+2^12+2^11;
Power(3,log3) mod p;
<Text-field style="Heading 1" layout="Heading 1">Exercise:</Text-field>Find the log base 5 of 7 in Z/p were p=65537JSFHLegal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.