{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 
0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 2 0 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 261 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal
" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 
1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 
"" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }
{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 
1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 
0 0 0 0 0 0 -1 0 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 
18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }
{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 
2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 25 "Pohlig-Hellman by Example
" }}{PARA 19 "" 0 "" {TEXT -1 36 "\251 Mike May, S.J., 2002,maymk@slu.
edu" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 242 "In looking at El Gamal and discrete logr
ithms we have mentioned Pohlig-Hellman as a method of solving the disc
reet log problem when p-1 has small prime factors.  The algorithm is c
omplicated enough that it is worthwhile to look at an example." }}}
{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 256 22 "Setting up the pr
oblem" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 183 "To set up the problem, w
e want a prime p chosen such that p-1 is a product of small primes, a \+
generator alpha of (Z_p)*, a randomly chosen a between 2 and p-1, and \+
beta=alpha^a mod p." }}{PARA 0 "" 0 "" {TEXT -1 47 "For the example we
 use 541 since 540=2^2*3^3*5." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 35 "p := 541;\nisprime(p);\nifactor(p-1);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"pG\"$T&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*()-%!G6#\"\"#F(\"\"\")-F&6#\"\"$F
-F)-F&6#\"\"&F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 149 "Next we want \+
a generator of  (Z_p)*.  To test if a number is a gererator, we try ra
ising it to the (p-1)/q power for each prime q that divides (p-1)." }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "testgen := x -> [Power(x,2
70) mod 541, Power(x, 180) mod 541, \n   Power(x, 54) mod 541];\ntestg
en(2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(testgenGf*6#%\"xG6\"6$%)o
peratorG%&arrowGF(7%-%$modG6$-%&PowerG6$9$\"$q#\"$T&-F.6$-F16$F3\"$!=F
5-F.6$-F16$F3\"#aF5F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"$S&\"
$H\"\"$8$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "Since none of these \+
powers is 1, our selected x is a generator.  Thus we choose alpha = 2.
  " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "alpha := 2;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%&alphaG\"\"#" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 218 "We now pick a at random.  (To make this worksheet repeat
able we fix a as the value that is produced by the random function fre
shly reseeded.)  We set our lower bound at 10 since we would like alph
a^a to be mode than p." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "a
 := rand(10..540)();\na := 238;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"aG\"$Q#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG\"$Q#" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 46 "Having alpha and a, we compute beta = alp
ha^a." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "beta := Power(alph
a, a) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%betaG\"#y" }}}}
{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 257 38 "Solving mod a pri
me to the first power" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 274 "Now we a
re ready to try to solve the discrete logrithm problem.  (We know alph
a and beta, but have forgotten a.)\nTo find a, it suffices to find a4,
 a27, and a5, the result of reducing a mod 4, 27, and 5.  We will star
t with a5 since 5 only appears to the first power in 540." }}{PARA 0 "
" 0 "" {TEXT -1 290 "We note that 4*27 is congruent to 0, 0, and 3 mod
 4, 27, and 5 respectively.  Since 3*2=1 mod 5 we know that 216 = 2*4*
27 is congruent to 0, 0, and 1 mod 4, 27, and 5 respectively.  Thus 21
6*a=a5 mod 540.  We compute alpha5 = alpha^216 and beta5 = beta^216.  \+
We note that beta5 = alpha5^a5." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 67 "beta5 := Power(beta, 216) mod p;\nalpha5 := Power(alpha, 216) \+
mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&beta5G\"#[" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%'alpha5G\"$S\"" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 48 "Now we compute the powers of alpha5 and find a5." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "for i from 0 to 4 do\nprint(
[i, Power(alpha5, i) mod p]) od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$
\"\"!\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"\"$S\"" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"#\"$C\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#7$\"\"$\"#[" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"%
\"$G#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "By inspection beta5 = ap
lha5^3.  Thus a5 = 3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "a5 \+
:= 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#a5G\"\"$" }}}}{SECT 0 
{PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 258 37 "Solving mod a prime to a \+
higher power" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 170 "We start a simila
r procedure for 27, the power of 3 in 540.  Since 4*5 = 20 mod 27 and \+
1/20=23 mod 27, we note that 460 = (0,1,0) mod (2, 27, 5).  Thus 460*a
=a27 mod 540." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "beta27 := \+
Power(beta, 460) mod p;\nalpha27 := Power(alpha, 460) mod p;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%'beta27G\"#m" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%(alpha27G\"$\\%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "We not
e that (alpha27)^27 = 1 mod p." }}{PARA 0 "" 0 "" {TEXT -1 33 "beta27 \+
= alpha27^a = alpha27^a27." }}{PARA 0 "" 0 "" {TEXT -1 48 "Describe a2
7 in base 3.  a27 = 9 x2 + 3 x1 + x0." }}{PARA 0 "" 0 "" {TEXT -1 40 "
We compute alpha27 ^ (9i) with i in Z_3." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 62 "for i from 0 to 2 do\nprint([i, Power(alpha27, 9*i) m
od p]) od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"!\"\"\"" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"\"$6%" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#7$\"\"#\"$H\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "Next we co
mpute beta27 ^ 9 = alpha27 ^ (9 x0) and read off x0." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 23 "Power(beta27, 9) mod p;" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#\"$6%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "Compar
ing with the list above, we see that x0=1." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 8 "x0 := 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G\"
\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "Now we compute beta27a =
 alpha27 ^(3 x1 + 9 x2) and beta27a ^ 3 = alpha27 ^ 9 x1, letting us r
ead off x1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "beta27a := b
eta27 * (Power(alpha27, 27-x0) mod p) mod p;\nPower(beta27a, 3) mod p;
\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(beta27aG\"$0&" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#\"$6%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 
"x1 := 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x1G\"\"\"" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 72 "Now we compute beta27b = alpha27 ^ (9 x2)
 and read off x2.  Compute a27." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 59 "beta27b := beta27a * (Power(alpha27, 27-x1*3) mod p) mod p;" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(beta27bG\"$H\"" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 29 "x2 := 2;\na27 := x2*9+x1*3+x0;" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%#x2G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
>%$a27G\"#A" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 259 27 "
Solving for the third prime" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Now
 we repeat for the process for the prime 2." }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 64 "temp := 27*5 mod 4;\ntemp2 := 1/temp mod 4;\npower
2 := temp2*27*5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%tempG\"\"$" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&temp2G\"\"$" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%'power2G\"$0%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 67 "beta4 := Power(beta, 405) mod p;\nalpha4 := Power(alpha, 405) \+
mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&beta4G\"$S&" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%'alpha4G\"$*[" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 61 "for i from 0 to 1 do\nprint([i, Power(alpha4, 2*i) mo
d p]) od:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"!\"\"\"" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"\"$S&" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 22 "Power(beta4, 2) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "x0 := 0;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G\"\"!" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 52 "beta4a := beta4 * (Power(alpha4, 4-x0) mod p) mod \+
p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'beta4aG\"$S&" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "x1 := 1;\na4 := x0 + 2*x1;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x1G\"\"\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#a4G\"\"#" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" 
}{TEXT 260 27 "Putting the parts together." }}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 230 "Now having a = (a4, a27, a5) mod (4, 27, 5).  We want to
 put them back together.  Since we already have 405, 460, and 216 equa
l to (1,0,0), (0,1,0), and (0,0,1) respectively mod (4,27,5), this is \+
a simple matter of multiplication." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 41 "a := (a4*405 + a27*460 + a5*216) mod 540;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%\"aG\"$Q#" }}}}{SECT 0 {PARA 4 "" 0 "" 
{TEXT -1 0 "" }{TEXT 261 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 136 "Choose a random number between 10 and 530 that is not a power \+
of 2.  Use the method given above to find its discreet log mod 541 bas
e 2." }}}{EXCHG }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}
{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 
33 1 1 }