{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 1 12 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 Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 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 1 }{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 1 }{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 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Geneva" 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 "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Geneva" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 4 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 }0 0 0 -1 -1 -1 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 "" 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" -1 18 1 {CSTYLE " " -1 -1 "Geneva" 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 "Geneva" 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 }{PSTYLE "Nor mal" -1 256 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 17 "Primality testing" }} {PARA 19 "" 0 "" {TEXT -1 38 "\251 Mike May, S. J., 2002, maymk@slu.ed u" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "Since we need large primes for the publi c key cryptosystems, we need methods to find if a number is prime with out finding factors," }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 264 40 "A simpl e procedure for primality testing" }{TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 173 "In class we looked at some probabilistic tests of p rimality. We want to see how effective the tests are. We will simply eyeball the results to see how well the tests work." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 278 "For the first test, we test for primality by using Fermat's little theorem. We test if n is prime by taking a random number a < n and seeing if a^(n-1) = 1 mod n . We have been told that if n is not prime we have at least a 50% cha nce of showing it by choosing a single number." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 139 "It is worthwhile checkin g out the effectiveness of this test with a specific n. The first tim e through we will look at the case of n = 77." }}{PARA 0 "" 0 "" {TEXT -1 65 "We first define a vector with all the numbers from 1 thro ugh n-1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "alphas := linal g[vector](76,i->i);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'alphasG-%'ve ctorG6#7ho\"\"\"\"\"#\"\"$\"\"%\"\"&\"\"'\"\"(\"\")\"\"*\"#5\"#6\"#7\" #8\"#9\"#:\"#;\"#<\"#=\"#>\"#?\"#@\"#A\"#B\"#C\"#D\"#E\"#F\"#G\"#H\"#I \"#J\"#K\"#L\"#M\"#N\"#O\"#P\"#Q\"#R\"#S\"#T\"#U\"#V\"#W\"#X\"#Y\"#Z\" #[\"#\\\"#]\"#^\"#_\"#`\"#a\"#b\"#c\"#d\"#e\"#f\"#g\"#h\"#i\"#j\"#k\"# l\"#m\"#n\"#o\"#p\"#q\"#r\"#s\"#t\"#u\"#v\"#w" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "Then we see what happens when we raise these numbers t o the n-1 power mod n." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "b etas := map(i-> [i,Power(i,76) mod 77], alphas);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&betasG-%'vectorG6#7ho7$\"\"\"F*7$\"\"#\"\"*7$\"\"$\" #D7$\"\"%F27$\"\"&\"#;7$\"\"'\"#r7$\"\"(\"#q7$\"\")\"#O7$F-F-7$\"#5\"# n7$\"#6FD7$\"#7\"#B7$\"#8\"#k7$\"#9FL7$\"#:FN7$F5F57$\"#<\"#g7$\"#=F27 $\"#>\"#e7$\"#?FJ7$\"#@\"#c7$\"#AFhn7$FGFG7$\"#C\"#`7$F0F07$\"#E\"#P7$ \"#FF87$\"#G\"#\\7$\"#HFN7$\"#IFW7$\"#JF\\o7$\"#KFB7$\"#L\"#W7$\"#MF*7 $\"#N\"#U7$F>F>7$F`oF`o7$\"#QFR7$\"#RFR7$\"#SF`o7$\"#TF>7$FepFep7$\"#V F*7$F`pF`p7$\"#XFB7$\"#YF\\o7$\"#ZFW7$\"#[FN7$FeoFeo7$\"#]F87$\"#^F`o7 $\"#_F07$F\\oF\\o7$\"#aFG7$\"#bFhn7$FfnFfn7$\"#dFJ7$FWFW7$\"#fF27$FRFR 7$\"#hF57$\"#iFN7$\"#jFL7$FJFJ7$\"#lFG7$\"#mFD7$FBFB7$\"#oF-7$\"#pF>7$ F;F;7$F8F87$\"#sF57$\"#tF27$\"#uF07$\"#vF-7$\"#wF*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 79 "Thus the test would tell us 77 is not prime if th e chosen a was anything except" }}{PARA 0 "" 0 "" {TEXT -1 315 "1, 34, 43, and 76. Thus the test indicates that n is not prime for 72 of 76 possible values of a. When we consider that the test is always incon clusive if a is 1 or -1, we see that the test indicates 77 not prime f or 72 of 74 possible values for a between 2 and n-2. That is consider ably more effective than 50%." }}}{EXCHG {PARA 5 "" 0 "" {TEXT 256 24 "Test some other numbers:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "The \+ following block of code is set up to test other numbers using the firs t test." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 98 "n := 131;\nalpha 1 := linalg[vector](n-1,i->i);\nbeta1 := map(i -> [i, Power(i, n-1) mo d n], alpha1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"$J\"" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%'alpha1G-%'vectorG6#7^s\"\"\"\"\"#\" \"$\"\"%\"\"&\"\"'\"\"(\"\")\"\"*\"#5\"#6\"#7\"#8\"#9\"#:\"#;\"#<\"#= \"#>\"#?\"#@\"#A\"#B\"#C\"#D\"#E\"#F\"#G\"#H\"#I\"#J\"#K\"#L\"#M\"#N\" #O\"#P\"#Q\"#R\"#S\"#T\"#U\"#V\"#W\"#X\"#Y\"#Z\"#[\"#\\\"#]\"#^\"#_\"# `\"#a\"#b\"#c\"#d\"#e\"#f\"#g\"#h\"#i\"#j\"#k\"#l\"#m\"#n\"#o\"#p\"#q \"#r\"#s\"#t\"#u\"#v\"#w\"#x\"#y\"#z\"#!)\"#\")\"##)\"#$)\"#%)\"#&)\"# ')\"#()\"#))\"#*)\"#!*\"#\"*\"##*\"#$*\"#%*\"#&*\"#'*\"#(*\"#)*\"#**\" $+\"\"$,\"\"$-\"\"$.\"\"$/\"\"$0\"\"$1\"\"$2\"\"$3\"\"$4\"\"$5\"\"$6\" \"$7\"\"$8\"\"$9\"\"$:\"\"$;\"\"$<\"\"$=\"\"$>\"\"$?\"\"$@\"\"$A\"\"$B \"\"$C\"\"$D\"\"$E\"\"$F\"\"$G\"\"$H\"\"$I\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&beta1G-%'vectorG6#7^s7$\"\"\"F*7$\"\"#F*7$\"\"$F*7$ \"\"%F*7$\"\"&F*7$\"\"'F*7$\"\"(F*7$\"\")F*7$\"\"*F*7$\"#5F*7$\"#6F*7$ \"#7F*7$\"#8F*7$\"#9F*7$\"#:F*7$\"#;F*7$\"#F*7$\"#?F* 7$\"#@F*7$\"#AF*7$\"#BF*7$\"#CF*7$\"#DF*7$\"#EF*7$\"#FF*7$\"#GF*7$\"#H F*7$\"#IF*7$\"#JF*7$\"#KF*7$\"#LF*7$\"#MF*7$\"#NF*7$\"#OF*7$\"#PF*7$\" #QF*7$\"#RF*7$\"#SF*7$\"#TF*7$\"#UF*7$\"#VF*7$\"#WF*7$\"#XF*7$\"#YF*7$ \"#ZF*7$\"#[F*7$\"#\\F*7$\"#]F*7$\"#^F*7$\"#_F*7$\"#`F*7$\"#aF*7$\"#bF *7$\"#cF*7$\"#dF*7$\"#eF*7$\"#fF*7$\"#gF*7$\"#hF*7$\"#iF*7$\"#jF*7$\"# kF*7$\"#lF*7$\"#mF*7$\"#nF*7$\"#oF*7$\"#pF*7$\"#qF*7$\"#rF*7$\"#sF*7$ \"#tF*7$\"#uF*7$\"#vF*7$\"#wF*7$\"#xF*7$\"#yF*7$\"#zF*7$\"#!)F*7$\"#\" )F*7$\"##)F*7$\"#$)F*7$\"#%)F*7$\"#&)F*7$\"#')F*7$\"#()F*7$\"#))F*7$\" #*)F*7$\"#!*F*7$\"#\"*F*7$\"##*F*7$\"#$*F*7$\"#%*F*7$\"#&*F*7$\"#'*F*7 $\"#(*F*7$\"#)*F*7$\"#**F*7$\"$+\"F*7$\"$,\"F*7$\"$-\"F*7$\"$.\"F*7$\" $/\"F*7$\"$0\"F*7$\"$1\"F*7$\"$2\"F*7$\"$3\"F*7$\"$4\"F*7$\"$5\"F*7$\" $6\"F*7$\"$7\"F*7$\"$8\"F*7$\"$9\"F*7$\"$:\"F*7$\"$;\"F*7$\"$<\"F*7$\" $=\"F*7$\"$>\"F*7$\"$?\"F*7$\"$@\"F*7$\"$A\"F*7$\"$B\"F*7$\"$C\"F*7$\" $D\"F*7$\"$E\"F*7$\"$F\"F*7$\"$G\"F*7$\"$H\"F*7$\"$I\"F*" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 257 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "1) Pick a nonprime number n between 100 and 1 50. Find out how many of the numbers between 2 and n-2 will show that n is composite." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "2) Repeat the previous exercise fo r another number between 100 and 150." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 263 37 "Procedure for testing higher numbers:" }{TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 217 "Obviously, we can't use this same procedure for large nu mbers because we will run out of memory trying to store the arrays. A simple alternative is to test with a running from 2 to 100. The proc edure is given below." }}{PARA 0 "" 0 "" {TEXT -1 21 "A simple prime t ester" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 309 "primetester := pr oc(n)\n local i, temp:\n for i from 2 to 100 do\n temp := Power(i ,n-1) mod n:\n if temp <> 1 then\n print(n,` is not prime`):\n print(cat(i,` ^ `,n-1,` = `,temp)):\n break:\n fi:od:\n \+ if i > 100 then print(cat(n,` is probably prime`)) fi:\n if i > 100 \+ then n else 0 fi:\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " primetester(1122334455667789);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"1* yncXMB7\"%.~is~not~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%G2~^~112 2334455667788~=~210589670002713G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\" \"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "primetester(131);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#%6131~is~probably~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$J\"" }}}{EXCHG {PARA 5 "" 0 "" {TEXT 258 14 "Finding primes" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 119 "Now that we c an test if a number is prime, we can try to find a prime by testing nu mbers in order until we find a prime" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 330 "findprime := proc(n)\n local temp, temp2, a, b, c: \n temp := rand(n)():\n print(\"The random number is \", temp):\n a := 0: \n c:= 0:\n while a = 0 do: \n b := primetester(temp):\n \+ temp := temp +1:\n c := c+1:\n if b <> 0 then a := 1: \n fi:o d:\n print(`After `,c-1,` unsuccessful tries, the prime number is `, \+ b):\n b:\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "Let us use th is procedure to find an 8 digit prime. We use the Maple command ispri me to test our answer." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "f indprime(10^8);\nisprime(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q6The~ random~number~is~6\"\")\"3p'>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\")\" 3p'>%.~is~not~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%82~^~19669080 ~=~14410911G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\")#3p'>%.~is~not~prim eG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%82~^~19669081~=~16997496G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\")$3p'>%.~is~not~primeG" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#%82~^~19669082~=~17251735G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\")%3p'>%.~is~not~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%72~^~19669083~=~8483156G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\") &3p'>%.~is~not~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%82~^~1966908 4~=~11647651G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\")'3p'>%.~is~not~pri meG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%82~^~19669085~=~16377674G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%;19669087~is~probably~primeG" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&%'After~G\"\"'%J~unsuccessful~tries,~t he~prime~number~is~G\")(3p'>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\")(3p '>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 259 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "3) Find two primes with 7 digits." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 160 "As \+ the size of the prime we are looking at grows, the number of tries nee ded also grows. Thus we want to modify the findprime so that it only \+ gives the answer." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 569 "prime tester2 := proc(n)\n local i, temp:\n for i from 2 to 100 do\n te mp := Power(i,n-1) mod n:\n if temp <> 1 then\n break:\n fi :od:\n if i > 100 then print(cat(n,` is probably prime`)) fi:\n if i > 100 then n else 0 fi:\nend:\nfindprime2 := proc(n)\n local temp, t emp2, a, b, c:\n temp := rand(n)():\n print(\"The random number is \+ \", temp):\n a := 0: \n c:= 0:\n while a = 0 do: \n b := primete ster2(temp):\n temp := temp +1:\n c := c+1:\n if b <> 0 then \+ a := 1: \n fi:od:\n print(`After `,c-1,` unsuccessful tries, the pri me number is `, b):\n b:\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "findprime2(10^20);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q6The~ra ndom~number~is~6\"\"5(ptIjV.F$p5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%G 10693270343633073709~is~probably~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%'After~G\"#7%J~unsuccessful~tries,~the~prime~number~is~G\"54P2L OMqKp5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"54P2LOMqKp5" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 265 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "4) Find primes with 10, 20, 30, 40, and 50 digi ts." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 25 "Oops - Carmichael numbers" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Let us try our test on 3828001 = 101*151*251 which i s clearly not prime." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "pri metester(3828001): isprime(3828001);ifactor(3828001);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%:3828001~is~probably~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(-%!G6#\"$ ,\"\"\"\"-F%6#\"$^\"F(-F%6#\"$^#F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 396 "The number 3828001 was specially chosen so that the order of t he multiplicative group divides n-1 even though n is not prime. Such \+ numbers are called Carmichael numbers. We would still spot the that n is not prime if we tested a number that is not relatively prime to n. Unfortunately, n was chosen so that its smallest prime factor is 101 . Thus we need to use the more sensative Miller test." }}}{EXCHG {PARA 5 "" 0 "" {TEXT 260 35 "The Miller-Rabin Test of primality." }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 120 "We also want to see what happens \+ with the more sophisticed test, the Miller-Rabin test. For that test \+ we factor n-1 as " }{XPPEDIT 18 0 "k*2^t" "6#*&%\"kG\"\"\")\"\"#%\"tGF %" }{TEXT -1 206 " for some odd number k. We then look at a raised to the powers k, 2*k, 2^2*k, ..., 2^t*k = n-1. If n is prime, then a^(n -1) = 1 mod n. Additionally, if a^(2j) = 1 mod n, then a^j mod n is e ither 1 or -1." }}{PARA 0 "" 0 "" {TEXT -1 52 "We illoustrate this tes t with n=77. We notice that " }{XPPEDIT 18 0 "76 = 2^2*19" "6#/\"#w*& \"\"#F&\"#>\"\"\"" }{TEXT -1 66 ". Thus we want to look at raising a \+ to the powers 19, 38, and 76." }}{PARA 0 "" 0 "" {TEXT -1 191 "For the Miller-Rabin test with a to fail to show n is composite,we need the l ast power to be 1. We also need for the previous power, if it exists, to be 1 or -1. Recall that 76 = -1 mod 77." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 112 "gammas := map(i -> \n [i, Power(i,19) mod 77, Power(i,38) mod 77, Power(i,76) mod 77],\n alphas);" } }{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'gammasG-%'vectorG6#7ho7&\"\"\"F*F* F*7&\"\"#\"#s\"#D\"\"*7&\"\"$\"#f\"#;F.7&\"\"%F.F/F57&\"\"&\"#vF5F37& \"\"'\"#8\"#:\"#r7&\"\"(\"#j\"#U\"#q7&\"\")\"#HF=\"#O7&F/F3F.F/7&\"#5F I\"#B\"#n7&\"#6FM\"#WFM7&\"#7FPFKFJ7&F;F:FF\"#k7&\"#9FB\"#\\FT7&F\"#SFfn\"#e7&\"#?\"# FFFFR7&\"#@Fbo\"#cFco7&\"#AFeoFeoFeo7&FJFJFKFJ7&FZFYF]o\"#`7&F.F5F3F.7 &\"#E\"#ZFhoFen7&F`oF_oF " 0 "" {MPLTEXT 1 0 1635 "WitnessTes t := proc(n)\nlocal n1, nprimelist, primelist, inconlist, i, numprime, numnprime,\n numincon, m, testlist, testlength, a, p1, p2,top:\ntop := min(n-1,101):\nn1 := n-1:\nnprimelist := []:\nprimelist := []:\n# \+ First we check that a^(n-1) = 1 mod n. \n# We break the numbers 2 to 100 into two groups, \n# those that show n is not prime, and\n# those that fail this test, but may work with more testing.\nfor i \+ from 2 to (top-1) do\n if ((Power(i,n-1) mod n) = 1) then primelist \+ := [op(primelist), i]:\n else nprimelist := [op(nprimelist), i]:\n \+ fi:\nod:\nnumnprime := linalg[vectdim](nprimelist):\n# Print the re sults up to this stage\nprint(cat(\"Testing a^\",n1,\" shows n is not \+ prime for \", numnprime,\n \" numbers\"));\nprint(nprimelist);\nm := n1:\n# The next step check to see if a^m = 1 or -1 when a^(2m) = 1 .\nwhile (m mod 2 = 0) do\n m := m/2:\n testlist := primelist: \n \+ testlength := linalg[vectdim](testlist);\n nprimelist := []:\n p rimelist := []:\n for i from 1 to testlength do\n a := testlist [i]:\n p1 := Power(a, 2*m) mod n:\n p2 := Power(a, m) mod n: \n if (p1 = 1) then \n if ((p2 <> 1) and (p2 <> n-1)) \n \+ then nprimelist := [op(nprimelist), a]: \n else \+ primelist := [op(primelist), a]:\n fi:\n else inconlist := [op(inconlist), a]:\n fi:\n od:\n numnprime := linalg[vectdi m](nprimelist):\n print(cat(\"Testing a^\",m,\" shows n is not prime for \", numnprime,\n \" additional numbers\"));\n print(nprime list);\nod:\nnumprime := linalg[vectdim](primelist):\nprint(cat(\"The \+ test fails for \", numprime,\" numbers\"));\nprint(sort(primelist)); \nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "WitnessTest( 3828001);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QUTesting~a^3828000~shows ~n~is~not~prime~for~0~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7 \"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QjnTesting~a^1914000~shows~n~is~ not~prime~for~0~additional~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QinTesting~a^957000~shows~n~ is~not~prime~for~0~additional~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QinTesting~a^478500~shows ~n~is~not~prime~for~0~additional~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QjnTesting~a^239 250~shows~n~is~not~prime~for~50~additional~numbers6\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7T\"\"#\"\"$\"\"(\"\")\"#5\"#6\"#7\"#:\"#=\"#E\"#F \"#G\"#H\"#K\"#M\"#N\"#Q\"#R\"#S\"#T\"#U\"#W\"#Y\"#[\"#]\"#^\"#`\"#b\" #d\"#f\"#g\"#h\"#i\"#j\"#m\"#n\"#p\"#s\"#t\"#u\"#v\"#$)\"#')\"#*)\"#!* \"#\"*\"#$*\"#%*\"#)*\"#**" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QjnTesti ng~a^119625~shows~n~is~not~prime~for~30~additional~numbers6\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7@\"\"%\"\"*\"#8\"#<\"#>\"#?\"#@\"#A\" #B\"#C\"#P\"#V\"#X\"#Z\"#\\\"#_\"#a\"#c\"#k\"#l\"#r\"#w\"#y\"#z\"#&)\" #()\"##*\"#&*\"#(*\"$+\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q?The~test ~fails~~for~19~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#75\"\"&\" \"'\"#9\"#;\"#D\"#I\"#J\"#L\"#O\"#e\"#o\"#q\"#x\"#!)\"#\")\"##)\"#%)\" #))\"#'*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 184 "Theortic arguments say that 3 of 4 numer s will witness that n is composite. Note that in our test case only 1 9 of the numbers from 2 through 100 fail to witness that n is not prim e. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 259 "Compare the results to a few other Carmichael numbers. With two Carmichael numbers we note th at the first primality test fails to identify them as composite number s, then note that the Miller test does identify them as composites, th en we factor the numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 128 "primetester(6733693): WitnessTest(6733693): ifactor(6733693);\n primetester(34657141): WitnessTest(34657141): ifactor(34657141);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%:6733693~is~probably~primeG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QUTesting~a^6733692~shows~n~is~not~prime~for ~0~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q[oTesting~a^3366846~shows~n~is~not~prime~for~51~add itional~numbers6\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7U\"\"#\"\"'\"\" )\"#5\"#6\"#8\"#9\"#<\"#=\"#>\"#B\"#C\"#I\"#K\"#L\"#P\"#R\"#S\"#T\"#U \"#W\"#Z\"#]\"#^\"#_\"#`\"#a\"#b\"#c\"#d\"#e\"#f\"#i\"#l\"#n\"#o\"#p\" #q\"#s\"#w\"#x\"#z\"#&)\"#')\"#!*\"#\"*\"##*\"#&*\"#'*\"#)*\"#**" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#Q[oTesting~a^1683423~shows~n~is~not~pr ime~for~34~additional~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7D \"\"$\"\"%\"\"&\"\"(\"#:\"#?\"#F\"#M\"#N\"#O\"#Q\"#V\"#X\"#Y\"#[\"#g\" #h\"#j\"#k\"#m\"#r\"#t\"#u\"#v\"#y\"#!)\"#$)\"#%)\"#()\"#))\"#*)\"#$* \"#%*\"$+\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q?The~test~fails~~for~1 4~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#70\"\"*\"#7\"#;\"#@\"# A\"#D\"#E\"#G\"#H\"#J\"#\\\"#\")\"##)\"#(*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(-%!G6#\"$4\"\"\"\"-F%6#\"$j\"F(-F%6#\"$z$F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%;34657141~is~probably~primeG" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#QVTesting~a^34657140~shows~n~is~not~prime~for~0~ numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q\\oTesting~a^17328570~shows~n~is~not~prime~for~49~addi tional~numbers6\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7S\"\"#\"\"'\"\") \"#5\"#8\"#9\"#=\"#>\"#A\"#B\"#C\"#H\"#I\"#K\"#M\"#P\"#R\"#S\"#T\"#U\" #V\"#Z\"#]\"#_\"#`\"#a\"#c\"#d\"#f\"#h\"#i\"#l\"#m\"#p\"#q\"#r\"#s\"#t \"#w\"#$)\"#()\"#))\"#*)\"#!*\"#\"*\"##*\"#&*\"#'*\"#)*" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#Q[oTesting~a^8664285~shows~n~is~not~prime~for~32 ~additional~numbers6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7B\"\"%\"\"& \"#6\"#7\"#:\"#<\"#E\"#G\"#J\"#L\"#N\"#O\"#Q\"#W\"#X\"#^\"#b\"#e\"#k\" #n\"#o\"#x\"#y\"#z\"#!)\"##)\"#%)\"#&)\"#')\"#$*\"#**\"$+\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q?The~test~fails~~for~18~numbers6\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#74\"\"$\"\"(\"\"*\"#;\"#?\"#@\"#D\"#F \"#Y\"#[\"#\\\"#g\"#j\"#u\"#v\"#\")\"#%*\"#(*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(-%!G6#\"$\">\"\"\"-F%6#\"$@%F(-F%6#\"$J%F(" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 118 "In these two cases respectively 8 6% and 82% of the numbers from 2 to 100 are witnesses that the numbers are not prime." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 262 8 "Exercise" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 201 "5) Pick 3 random \+ 50 digit numbers. Test if each to see if it is prime and if it is com posite, note the percentage of choices of a from 2 to 100 that will sh ow they are composite with the Miller test." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 329 "It is wo th noting that we have yet to find a composite n that we can't show to be composite by testing the number 2. Such a number would be called \+ a strong probable-prime base 2. It has been shown in the literature t hat letting the base range over the primes less than 20 will correctly identify all composites less than 10^15." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "We can clean up the code and give a better prime finding routine. In particular we eliminate the printing of the unsuccessful tries" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 892 "primetester4 := \+ proc(n)\n local a, temp, temp2, k, m:\n temp2 := n:\n k:= n-1:\n while (k mod 2 = 0) do k:= k/2 od:\n for a from 2 to 100 do\n m := k:\n \+ temp := Power(a,k) mod n:\n if ((temp = 1) or (temp = n-1)) then break:\n else while (m < n-1) do\n m := 2*m:\n temp : = Power(temp,2) mod n:\n if (temp = n-1) then break:\n e lif (temp = 1) then temp2 := 0: break: \n fi:\n od:\n i f ((m = n-1) and (temp <> 1)) then temp2 := 0 fi:\n fi:\n if (te mp2 = 0) then break fi:\n od:\n temp2;\nend:\nfindprime4 := proc(n)\n \+ local temp, a, b, c:\n temp := rand(n)():\n temp := temp + (1 - irem(t emp,2)):\n print(`the random number is `, temp):\n a := 0: \n c:= 0:\n while a = 0 do: \n b := primetester4(temp):\n temp := temp \+ +2:\n c := c+1:\n if b <> 0 then a := 1: fi:\n od:\n print (`After `,c-1,` unsuccessful tries, the prime number is `, b):\n b:\ne nd:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "findprime4(10^100); \+ isprime(%);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6$%6the~random~number~is~ G\"_qjr[v+JbE&>\")f#4u.!eX<#Rh0Vgo<7uHs&3AA1K!Q0$QvYn(*=(e%eNc$" }} {PARA 12 "" 1 "" {XPPMATH 20 "6&%'After~G\"$.\"%J~unsuccessful~tries,~ the~prime~number~is~G\"_qpt[v+JbE&>\")f#4u.!eX<#Rh0Vgo<7uHs&3AA1K!Q0$Q vYn(*=(e%eNc$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"_qpt[v+JbE&>\")f#4u .!eX<#Rh0Vgo<7uHs&3AA1K!Q0$QvYn(*=(e%eNc$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" } {TEXT 261 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 69 "6) Use \+ the findprime4 procedure to find 60, 70, and 80 digit primes." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 " " {TEXT -1 32 "Maple's method of finding primes" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "It is worthwhile seeing how Maple finds primes with \+ the nextprime command." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "n extprime(rand(10^10)());" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+j/\\zr " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "We can look at the code used \+ with the showstat command." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "showstat(nextprime);" }{TEXT -1 0 "" }}{PARA 6 "" 1 "" {TEXT -1 0 "" }}{PARA 6 "" 1 "" {TEXT -1 20 "nextprime := proc(n)" }}{PARA 6 "" 1 "" {TEXT -1 12 "local i, t1;" }}{PARA 6 "" 1 "" {TEXT -1 30 " 1 \+ if type(n,integer) then" }}{PARA 6 "" 1 "" {TEXT -1 22 " 2 if n \+ < 2 then" }}{PARA 6 "" 1 "" {TEXT -1 12 " 3 2" }}{PARA 6 "" 1 "" {TEXT -1 13 " else" }}{PARA 6 "" 1 "" {TEXT -1 32 " 4 \+ if irem(n,2) = 0 then" }}{PARA 6 "" 1 "" {TEXT -1 22 " 5 \+ t1 := n+1" }}{PARA 6 "" 1 "" {TEXT -1 15 " else" }}{PARA 6 " " 1 "" {TEXT -1 22 " 6 t1 := n+2" }}{PARA 6 "" 1 "" {TEXT -1 18 " end if;" }}{PARA 6 "" 1 "" {TEXT -1 53 " 7 f or i from t1 by 2 while not isprime(i) do" }}{PARA 6 "" 1 "" {TEXT -1 17 " 8 NULL" }}{PARA 6 "" 1 "" {TEXT -1 18 " end d o;" }}{PARA 6 "" 1 "" {TEXT -1 12 " 9 i" }}{PARA 6 "" 1 "" {TEXT -1 15 " end if" }}{PARA 6 "" 1 "" {TEXT -1 32 " el if type(n,numeric) then" }}{PARA 6 "" 1 "" {TEXT -1 41 " 10 error \"argument must be integer\"" }}{PARA 6 "" 1 "" {TEXT -1 11 " e lse" }}{PARA 6 "" 1 "" {TEXT -1 23 " 11 'nextprime(n)'" }}{PARA 6 "" 1 "" {TEXT -1 13 " end if" }}{PARA 6 "" 1 "" {TEXT -1 8 "en d proc" }}{PARA 6 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 188 "This is essentially the same algorithm we used. From th e starting point, check odd numbers going up untill a prime is found. \+ We then want to see how Maple checks is=if a number is prime." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "showstat(isprime);" }}{PARA 6 "" 1 "" {TEXT -1 0 "" }}{PARA 6 "" 1 "" {TEXT -1 18 "isprime := proc (n)" }}{PARA 6 "" 1 "" {TEXT -1 21 "local btor, nr, p, r;" }}{PARA 6 " " 1 "" {TEXT -1 36 " 1 if not type(n,'integer') then" }}{PARA 6 " " 1 "" {TEXT -1 34 " 2 if type(n,'numeric') then" }}{PARA 6 "" 1 "" {TEXT -1 46 " 3 error \"argument must be an integer\"" }} {PARA 6 "" 1 "" {TEXT -1 13 " else" }}{PARA 6 "" 1 "" {TEXT -1 30 " 4 return 'isprime(n)'" }}{PARA 6 "" 1 "" {TEXT -1 15 " end if" }}{PARA 6 "" 1 "" {TEXT -1 14 " end if;" }} {PARA 6 "" 1 "" {TEXT -1 20 " 5 if n < 2 then" }}{PARA 6 "" 1 "" {TEXT -1 14 " 6 false" }}{PARA 6 "" 1 "" {TEXT -1 38 " eli f member(n,`isprime/w`) then" }}{PARA 6 "" 1 "" {TEXT -1 13 " 7 \+ true" }}{PARA 6 "" 1 "" {TEXT -1 67 " elif igcd(2305567963945518 424753102147331756070,n) <> 1 then" }}{PARA 6 "" 1 "" {TEXT -1 14 " \+ 8 false" }}{PARA 6 "" 1 "" {TEXT -1 26 " elif n < 10201 then " }}{PARA 6 "" 1 "" {TEXT -1 13 " 9 true" }}{PARA 6 "" 1 "" {TEXT -1 409 " elif igcd(849696948923341811053233990918734996592 6062586648932736611545426342203893270769390909069477309509137509786917 1186680288614993338250976823867229837379629630667576741311267365789364 4078815718696989373063311306647862044862494925732402262739543736363903 8752608166758661255956834630697220447512298848222228550062683786342519 960225996301315945644470064720696621750477244528915927867113,n) <> 1 t hen" }}{PARA 6 "" 1 "" {TEXT -1 14 " 10 false" }}{PARA 6 "" 1 "" {TEXT -1 28 " elif n < 1018081 then" }}{PARA 6 "" 1 "" {TEXT -1 13 " 11 true" }}{PARA 6 "" 1 "" {TEXT -1 11 " else" }} {PARA 6 "" 1 "" {TEXT -1 38 " 12 nr := igcd(408410100000,n-1);" } }{PARA 6 "" 1 "" {TEXT -1 30 " 13 nr := igcd(nr^5,n-1);" }}{PARA 6 "" 1 "" {TEXT -1 27 " 14 r := iquo(n-1,nr);" }}{PARA 6 "" 1 "" {TEXT -1 40 " 15 btor := modp(('power')(2,r),n);" }}{PARA 6 "" 1 "" {TEXT -1 242 " 16 if `isprime/cyclotest`(n,btor,2,r) = false o r irem(nr,3) = 0 and `isprime/cyclotest`(n,btor,3,r) = false or irem(n r,5) = 0 and `isprime/cyclotest`(n,btor,5,r) = false or irem(nr,7) = 0 and `isprime/cyclotest`(n,btor,7,r) = false then" }}{PARA 6 "" 1 "" {TEXT -1 23 " 17 return false" }}{PARA 6 "" 1 "" {TEXT -1 16 " \+ end if;" }}{PARA 6 "" 1 "" {TEXT -1 31 " 18 if isqrt(n)^2 = n then" }}{PARA 6 "" 1 "" {TEXT -1 23 " 19 return false" }} {PARA 6 "" 1 "" {TEXT -1 16 " end if;" }}{PARA 6 "" 1 "" {TEXT -1 63 " 20 for p from 3 while numtheory[jacobi](p^2-4,n) <> -1 do" }}{PARA 6 "" 1 "" {TEXT -1 15 " 21 NULL" }}{PARA 6 "" 1 "" {TEXT -1 16 " end do;" }}{PARA 6 "" 1 "" {TEXT -1 54 " 2 2 evalb(`isprime/TraceModQF`(p,n+1,n) = [2, p])" }}{PARA 6 "" 1 " " {TEXT -1 13 " end if" }}{PARA 6 "" 1 "" {TEXT -1 8 "end proc" }}{PARA 6 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 487 "The isprime routine first check if the test candidate n is in the list of primes below 100. If not it checks to see if any of those pr imes divide n by computing the gcd of n and the product of primes less than 100, thus testing if n is a prime less than (101)^2. If not, it computes the gcd of n and the product of primes less than 1000 to tes t for primes less than (1009)^2. Failing to find that n has any small factors, Maple then turns to techniques beyond the scope of this clas s " }}}{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 }