{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 } {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 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{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 "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 11 "Safe Primes" }}{PARA 19 " " 0 "" {TEXT -1 36 "\251Mike May, S.J., 2002, maymk@slu.edu" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 174 "For various public key cryptosystems, we want a l arge prime p where p-1 has a sufficiently large factor. It is worthwh ile to explore how we can find such primes efficiently." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 28 "Efficiently finding 2-primes" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 243 "We want to begin with a test that is fai rly efficient and generally finds a prime. We recall that for any ran dom composite n we tested 2^(n-1) was not congruent to 1 mod (n-1). T his leads to a simple test for numbers that are probably prime." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 153 "test := rand(10^100)();\nif ((test mod 2) = 0) then test := test + 1 fi:\nwhile((Power(2,test-1) m od test)<>1) do\ntest := test + 2:\nod:\ntest;\nisprime(test);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%%testG\"_q@Rh0Vgo<7uHs&3AA1K!Q0$QvYn (*=(e%eNcVhDuuptIjV.F$p56K\"3*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"_q LWh0Vgo<7uHs&3AA1K!Q0$QvYn(*=(e%eNcVhDuuptIjV.F$p56K\"3*" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 336 "The test is fairly inefficient, since with each odd candidatewe use m odular exponentiation of 2 to a large power, which is a long operation . We would like to eliminate most candidates by noting that they shar e a factor with a small prime. To do that we compute the product of t he primes less than 100, and the primes from 100 to 1000." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 258 "smallPrimes := 2:\ntestp := 2:\nwh ile (testp < 100) do\ntestp := nextprime(testp):\nsmallPrimes := small Primes*testp:\nod:\nsmallPrimes:\nmedPrimes := 101:\ntestp := 101:\nwh ile (testp < 1000) do\ntestp := nextprime(testp):\nmedPrimes := medPri mes*testp:\nod:\nmedPrimes:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "Th is gives a faster test for 2-primes, which we turn into a procedure. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 392 "next2prime := proc(n) \n local test, doneTest:\n test := n:\n if((test mod 2) = 0) the n test := test + 1 fi:\n doneTest := 0:\n while (doneTest = 0) do \n if (igcd(smallPrimes,test)<>1) then test := test + 2:\n e lif (igcd(medPrimes,test)<>1) then test := test + 2:\n elif ((Pow er(2,test-1) mod test)<>1) then test := test + 2:\n else doneTest := 1: fi:\n od:\n test;\nend:" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 32 "Finding safe 2-primes. (p=2*q+1)" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 314 "Ideally, for El Gamal, we would like to use a safe or No ether prime. These have the form form 2q+1 where q is also prime. T hese primes are obviously rarer, so it will take longer to find them. \+ Thus our first pass at a procedure to find these primes will print ou t progress reports after every 20 q that we try." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 602 "test:= next2prime(rand(10^50)());\n doneTe st := 0:\n count := 1;\n while (doneTest = 0) do\n test2 := 2 *test+1;\n if (igcd(smallPrimes,test2)<>1) then \n test : = next2prime(test+2):\n count := count +1:\n elif (igcd(m edPrimes,test2)<>1) then \n test := next2prime(test+2):\n \+ count := count +1:\n elif ((Power(2,test2-1) mod test2)<>1) t hen \n test := next2prime(test+2):\n count := count +1 :\n else doneTest := 1: fi:\n if (count mod 20 = 0) then pri nt(count, test, test2) fi;\n od:\nprint(count, test, test2);\nisprim e(test2);\ntest2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%testG\"R.Ufp\" RqX!\\zrzjr[v+JbE&>\")f#*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&countG \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\")\"RT`fp\"RqX!\\zrzjr[v+ JbE&>\")f#*\"S$o!>R$yS\"4)*eVfFV(4:?1J0Ri>&=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"S$o!>R$yS \"4)*eVfFV(4:?1J0Ri>&=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 475 " nextsafe2prime := proc(n)\n local test, test2, doneTest:\n doneTes t := 0:\n test := iquo(n,2)+1:\n test2 := 2*test+1;\n while (don eTest = 0) do\n test2 := 2*test+1;\n if (igcd(smallPrimes,te st2)<>1) then \n test := next2prime(test+2):\n elif (igcd (medPrimes,test2)<>1) then \n test := next2prime(test+2):\n \+ elif ((Power(2,test2-1) mod test2)<>1) then \n test := next 2prime(test+2):\n else doneTest := 1: fi:\n od:\n test2;\nend :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "p1 := nextsafe2prime(r and(10^40)());\nisprime(p1);\nnumtheory[factorset](p1-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p1G\"I*\\Oqu`k\"zX?H\"e3M))\\g\\n\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$\"\"#\"H\\#=N(oAe*G-Y1H/<%\\-[P)" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 50 "Finding primes where p-1 has a large prime factor." }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 225 "For other uses we don't need to r estrict our primes so tightly. Generally, we simply want a prime of t he form p=qk+1 where q is sufficiently large. Suppose we want a 100 d igit prime of this form where q should be 40 digits." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 554 "q := next2prime(rand(10^39..10^40)());\n k := rand(10^60)();\n doneTest := 0:\n count := 1;\n while (done Test = 0) do\n test := 2*q*k+1;\n if (igcd(smallPrimes,test)<>1 ) then \n k := k+1:\n count := count +1:\n elif ( igcd(medPrimes,test)<>1) then \n k := k+1:\n count := \+ count +1:\n elif ((Power(2,test-1) mod test)<>1) then \n \+ k := k+1:\n count := count +1:\n else doneTest := 1: fi: \n if (count mod 50 = 0) then print(count, test) fi;\n od:\npri nt(count, q, k, test);\nisprime(test);\ntest;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"Ix#[ZTYh3IN0^*\\t%\\i?zI*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"kG\"gnmP$H)fnu$*4g(>7)*31gsK(4^Ga_4Pn#RH%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&countG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#]\"_qdp2B&\\=Rb(pX$**>_h]Gw(fE(fw\\AyxNb@\"*yW$))>G \"yBU**)eVkZe]$*z" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$+\"\"_qdY!z*4 \\1SwA*R]>()3+\"ppn>)fw\\AyxNb@\"*yW$))>G\"yBU**)eVkZe]$*z" }}{PARA 12 "" 1 "" {XPPMATH 20 "6&\"$S\"\"Ix#[ZTYh3IN0^*\\t%\\i?zI*\"gn0R$H)fn u$*4g(>7)*31gsK(4^Ga_4Pn#RH%\"_qrLE2q\\q5B7j-\"*)plC#=>+'*)fw\\AyxNb@ \"*yW$))>G\"yBU**)eVkZe]$*z" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"_qrLE2q\\q5B7j-\"*)plC#=>+'*)fw \\AyxNb@\"*yW$))>G\"yBU**)eVkZe]$*z" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 436 "nextnice2prime := proc(qstart, kstart)\n local q, \+ k, test, test2, doneTest:\n q := next2prime(qstart);\n k := kstart ;\n doneTest := 0:\n while (doneTest = 0) do\n test := 2*q*k+1; \n if (igcd(smallPrimes,test)<>1) then \n k := k+1:\n \+ elif (igcd(medPrimes,test)<>1) then \n k := k+1:\n elif ((Power(2,test-1) mod test)<>1) then \n k := k+1:\n else doneTest := 1: fi:\n od:\n [q, k, test];\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "For digital signatures, we will ant p to be ch osen as a 512 bit prime of the form p=qk+1 where q is a 128 bit prime. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "p1 := nextnice2prime(ra nd(2^128)(),rand(2^384)());\nisprime(p1[3]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#p1G7%\"H.\\(Rq(HtMMnQ\"o>oVm!)G8\"_r@'3(QkNL/8X)=-,4 #*3f!fUV6$e&e\"*\\!4IkyJH2^;sNu,73a[oB99\"4E[)f8**Q `*>\"3l=e,'*\\R&H6B$[AZ!pU4e<_%)y6&p/@5F/$3&ew?)4%*R]OB?wZm)[O\"3h!z[_ 5[S*\\t#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p1[2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"_r@'3(QkNL/8X)=-,4#*3f!fUV6$e&e\"*\\!4IkyJH2^;sNu,73a[oB99\"4E " 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 }