{VERSION 5 0 "IBM INTEL LINUX" "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 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }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 1 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "MAS3008 -- SOLUTIONS TO MA PLE EXERCISES" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 195 "An executable MAPLE worksheet containing implementations of the various algorithms can be downloaded from the Module Web page. Alternatively, you might like to write your own procedures, as below " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "EXERCISE 1" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "(a)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "p:=nextprime(100000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"p G\"'.+5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "2^(p-1) mod p; \+ " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 15 "2&^(p-1) mod p;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 134 "We can measure the CPU time taken (in seconds) using the time() command: using the 2nd method of taking powers, the \+ time is negligible" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "time(2^(p-1) \+ mod p);time(2&^(p-1) mod p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"#D! \"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"\"!F$" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 31 "Now try a much larger prime... " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "p:=nextprime(1000000);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"(.++\"" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "2^(p-1) mod \+ p;2&^(p-1) mod p; time(2^(p-1) mod p);time(2&^(p-1) mod p); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\" \"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"%v6!\"$" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#$\"\"!F$" }}}{EXCHG {PARA 11 "" 1 "" {TEXT -1 0 "" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "(b)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 154 "powermod:=proc(a,k,n) local b,c,i;c:=a;b:=1;i:=k;\nwhile i>0 \+ do\n if (i mod 2=1) then b:=b*c mod n; i:=i-1;fi;\n c:=c*c mod n; i: =i/2;\nod;\nRETURN(b);\nend:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "powermod(29,405, 1347);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$L#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "p1:=nextprim e(2^20);p2:=nextprime(2^30);p3:=nextprime(2^50);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p1G\"($e[5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p2G \"+F=ut5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p3G\"1zE%o!***e7\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "powermod(3,p1-1,p1);powermod (5,p2-1,p2);powermod(7,p3-1,p3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\" \"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "ti me(powermod(7,p3-1,p3));" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }{XPPMATH 20 "6#$\"\"\"!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "(c) Now try \+ same thing using a simple loop...." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "powermod2:=proc(a,k,n) loca l b,i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "b:=1;" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 38 "for i from 1 to k do b:=b*a mod n; od;" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 10 "RETURN(b);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "powermod2(2,256,257);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "p1:=nextprime(2^20);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p1G\"($e[5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "powermo d2(2,p1-1,p1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "time(powermod2(2,p1-1,p1));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#$\"%j[!\"$" }}}{EXCHG {PARA 11 "" 1 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "This is vastly slower ! " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Exerci se 2." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=2212374139;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"nG\"+RTP7A" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod( 2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+Nitl>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "This shows n is not prime..." }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "isprime(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"%P$*\"\"\"-F%6#\"'ZpBF(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "n:=19707683773;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"nG\",tPo2(>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7, n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 19 "powermod(11,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "po wermod(13,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 185 "These are consistent with n being prime: if n is not prime then it is a pseudoprime to all the bases 2, 3, 5, 7, 11, 13. (This is unlikely unless n was contrived to have thi s property.)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "isprime(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 68 "Now look for 10-digit numbers pass ing Fermat test to bases 2,3,5,7: " }}{PARA 0 "" 0 "" {TEXT -1 115 "Th is can be done by trial and error (or alternatively, you could progra mme a loop to search for suitable numbers)." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=1234 567891;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+\"*ycM7" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n1:=n;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n1G\"+\"*ycM7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=2395806251;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+^i!eR#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "po wermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n2:=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n2G\"+^i! eR#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=2134642231;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+JAkM@" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "po wermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n3:=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n3G\"+JAkM@" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=7232632703;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+.FjKs " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n4:=n;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n4G\"+.FjKs" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 14 "n:=3272052041;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+T?0sK" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "pow ermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n5:=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n5G\"+T?0 sK" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=2425472839;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+RGZDC" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "po wermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n6:=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n6G\"+RGZDC" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=2637564901;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+,\\cP E" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n7:=n;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n7G\"+,\\cPE" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 14 "n:=1362385309;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+4`Qi8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "pow ermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n8:=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n8G\"+4`Q i8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=3960384521;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+@XQgR" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "po wermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n9:=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n9G\"+@XQgR" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=1524831907;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+2>$[_ \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(2,n-1,n);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(5,n-1,n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n10:=n;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$n10G\"+2>$[_\"" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 31 "n1;n2;n3;n4;n5;n6;n7;n8;n9;n10;" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+\"*ycM 7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+^i!eR#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+JAkM@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+.FjKs" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+T?0sK" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+RGZDC" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+,\\cPE" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+4`Qi8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+@XQgR" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"+2>$[_\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%tru eG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n3);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%tru eG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n5);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%tru eG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n7);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%tru eG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(n9);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "isprime(n10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%tr ueG" }{MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 221 "We've now foun d ten 10-digit numbers passing the Fermat test to bases 2, 3, 5, 7; an d in fact all of them are primes. The Fermat test is fairly good - mos t numbers that pass to base 2 are prime. But of course, not all ..." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=1001152801;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"nG\"+,G:,5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(2, n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 18 "powermod(3,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "po wermod(5,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "powermod(7,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*,-%!G6#\"#6\"\"\"- F%6#\"#TF(-F%6#\"#hF(-F%6#\"$^\"F(-F%6#\"$T#F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "For each of the primes p dividing n, we have that p- 1 divides n-1." }}{PARA 0 "" 0 "" {TEXT -1 176 "Hence n is a Carmichae l number, and it will pass the Fermat primality test to any base a wit h gcd(a,n)=1. It will fail if gcd(a,n)>1, e.g. if a is any of the prim es dividing n:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "powermod(11,n-1,n );powermod(41,n-1,n);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"*6*Q,\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"*`vQ\"y" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 38 "powermod(13,n-1,n);powermod(43,n-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\" \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Exerc ise 3:" }}{PARA 0 "" 0 "" {TEXT -1 43 "Miller-Rabin test for stong pse udoprimes. :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "spsp:=proc(n,a) local g,m,s,b,b1,i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "if a>=n or a<2 then RETURN(`Invalid input`) fi; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "if n mod 2=0 then RETURN(`Fail: factor`,2) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "g:=gcd(a,n); if \+ g>1 then RETURN(`Fail: factor`,g) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "m:=n-1; s:=0;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "while m mod \+ 2=0 do m:=m/2; s:=s+1 od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "b:=pow ermod(a,m,n);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "if b=1 then RETURN (Pass) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if b=n-1 then RETURN( Pass) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "for i from 1 to s-1 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "b1:=b*b mod n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "if b1=1 then RETURN(`Fail: factor`,gcd(b-1,n)) f i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "if b1=n-1 then RETURN(Pass) f i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "b:=b1;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "RETURN(Fail) ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 53 "Test detection of invaild input and special cases \+ ..." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "spsp(561,1);spsp(561 ,561);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "spsp(56,2);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#%.Invalid~inputG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%.Invalid~inputG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail:~fact orG\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 24 "Now try it \"for real \" .." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "spsp(567,7);" } {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail:~factorG\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "spsp(561,2);" }}{PARA 0 " " 0 "" {TEXT -1 43 "Try it out on examples done in lectures ..." }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail:~factorG\"#L" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "spsp(2047,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%PassG" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "spsp(2047,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n :=1373653;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"(`OP\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "spsp(n,2);spsp(n,3);spsp(n,5 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%PassG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%PassG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Now try numbers from Question 2" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "n:=221237139; spsp(n,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"*RrB@#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "n :=19707683773; spsp(n,2);spsp(n,3);spsp(n,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\",tPo2(>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%Pa ssG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%PassG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%PassG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=1001152801;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"+,G: ,5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "spsp(n,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail:~factorG\"(hT:%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "ifactor(4154161);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#**-%!G6#\"#6\"\"\"-F%6#\"#TF(-F%6#\"#hF(-F%6#\"$^\"F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 129 "So the Carmichael number in Qu estion 2 is detected by the Miller-Rabin test at the first attempt (ba se 2). Other bases work too.." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "spsp(n,3); spsp(n,5); spsp(n,7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail:~factorG\"'@85" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail: ~factorG\"(hT:%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%-Fail:~factorG\"(h T:%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Ques tion 4: Pollard p-1 method:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "(a)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 196 "pollard:=proc(n,a0,kmax) local a,g,k;a:=a0;\nfor k from 2 to kmax do\n a:=powermod(a,k,n);\n g:=gcd(a-1,n);\n if g=n then RETURN(Fai l1); fi;\n if g>1 then RETURN(g,n,k) fi;\nod;\nRETURN(Fail2);\nend:\n " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "pollard(403,2,1000);pol lard(1891,2,1000);pollard(5157437,2,1000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#8\"$.%\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fai l1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"%pA\"(Pu:&\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "ifactor(1891);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"#J\"\"\"-F%6#\"#hF(" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 238 "So the 1st and 3rd values of n are easily factorised ( using base 2). For n=1891=31 x 61, both prime factors show up together at step 5, so we can't factorise n by this method unless we are parti cularly lucky, (as happens here for base 5):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "pollard(1891,3,100); pollard(1891,5,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6% \"#J\"%\"*=\"\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "Now try it f or the Fermat numbers. As these are closely related to powers of 2, we wouldn't expect base 2 to work." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "F5:=2^3 2+1;F6:=2^64+1;F7:=2^128+1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F5G \"+(Hn\\H%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F6G\"5<;b4P2WnW=" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F7G\"Hd9@o " 0 "" {MPLTEXT 1 0 18 "pollard(F5,2,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "However, other bases should be OK" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "pollard(F5,3,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 %\"$T'\"+(Hn\\H%\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "po llard(F6,3,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'xTF\"5<;b4P2WnW =\"#<" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pollard(F7,3,1000) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "So F5 and F6 are easily factorised by this method. F7 is much harder to factorise, although it is composite:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "isprime(F7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " pollard(F7,5,1000);pollard(F7,11,1000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "(b) First identify composite Mersenne numbers Mp for p<100:" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for p from 2 to 99 do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "if isprime(p) then if not isprime(2 ^p-1) then print(p);fi;fi;od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6 " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#H" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#P" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"#T" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#V" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"#Z" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#\"#`" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#f" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#r" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#t" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#z " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#$)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#(*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "So there are 15 values of p to consider, viz 11, 23, 29, 37, 41, 43, 47, 53, 5 9, 67, 71, 73, 79, 83, 97" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "M11:=2^11-1;M23:=2^23- 1;M29:=2^29-1;M37:=2^37-1;M41:=2^41-1;M43:=2^43-1;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%$M11G\"%Z?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M2 3G\"(2')Q)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M29G\"*64(o`" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M37G\"-rM&*Qu8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M41G\".^bDB!*>#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %$M43G\".2A-$4'z)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "M47:=2 ^47-1;M53:=2^53-1;M59:=2^59-1;M67:=2^67-1;M71:=2^71-1;M73:=2^73-1;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M47G\"0F`N)[P29" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%$M53G\"1\"*4ua#*>2!*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M59G\"3([BMI_2Yw&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M67G \"6FHTw'*e_RdZ\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M71G\"7ZogA[VTK =hB" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M73G\"7\"RF/HRd'HtW%*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "M79:=2^79-1;M83:=2^83-1;M97: =2^97-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M79G\"9(3`te9t!)4HY/'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M83G\":2%\\wRLq\"pb19n*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$M97G\"?r1!z3(=v'G&G]Kc%e\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pollard(M11,2,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 125 " We cannot factor any of these using base 2 for Pollard's p-1 method, s ince 2 must have order p for any prime factor q of Mp. " }}{PARA 0 "" 0 "" {TEXT -1 10 "Try base 3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M11,3,200);pollard(M23,3,200);pollard(M29,3,200);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#Z\"(2')Q)\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M37,3,200);pollard( M41,3,200);pollard(M43,3,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$B #\"-rM&*Qu8\"#P" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"&nL\"\".^bDB!*># \"$j\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$J%\".2A-$4'z)\"#V" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M47,3,200);pollard(M 53,3,200);pollard(M59,3,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\")j+ h5\"0F`N)[P29\"#Z" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"-hZyG(H\"\"1\"* 4ua#*>2!*\"#`" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'^*z\"\"3([BMI_2Yw& \"#h" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M67,3,200); pollard(M71,3,200);pollard(M73,3,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$R%\"7\"RF/HRd'HtW%*\"#t" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M79,3,200);pollard(M83,3,200);pol lard(M97,3,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"%(o#\"9(3`te9t!) 4HY/'\"#z" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$n\"\":2%\\wRLq\"pb19n* \"#$)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"&Z9\"\"?r1!z3(=v'G&G]Kc%e\" \"#(*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 117 "Using kmax=200 we facto rise all cases except p=11, 29, 67, 71. The latter 2 cases can be hand led by increasing kmax: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "pollard(M67,3,5000); pollard(M71,3,5000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"*@xq$>\"6FHTw'*e_RdZ\"\"%xE" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'z%G#\"7ZogA[VTK=hB\"%4;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 119 "However p=11 and p-29 can't - notice the program halts \+ with Fail1 in these cases but Fail2 in the preceding two cases." }} {PARA 0 "" 0 "" {TEXT -1 73 "We can explain this by looking at the pri me factorisation of M11 and M29:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "ifactor (M11);ifactor(M29);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"#B\" \"\"-F%6#\"#*)F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(-%!G6#\"$L#\"\" \"-F%6#\"%.6F(-F%6#\"%*3#F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "ifactor(232);ifactor(1102);ifactor(2088);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&)-%!G6#\"\"#\"\"$\"\"\"-F&6#\"#HF*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#*(-%!G6#\"\"#\"\"\"-F%6#\"#>F(-F%6#\"#HF(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*()-%!G6#\"\"#\"\"$\"\"\")-F&6#F)F(F*-F&6#\" #HF*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 296 "For p=11, the prime fact ors q=23, 89 both have p-1 dividing k! for the first time when k=22; \+ and for p=29 all 3 factors q have q-1 dividing k! for the first time \+ when k=29. Thus these composite numbers cannot be factorised by the p -1 method (unless there is a \"fluke\" with the choice of base)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "Now try again with a=5:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 57 "pollard(M11,5,200);pollard(M23,5,200);pollard( M29,5,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}{PARA 11 " " 1 "" {XPPMATH 20 "6%\"#Z\"(2')Q)\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M 37,5,200);pollard(M41,5,200);pollard(M43,5,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$B#\"-rM&*Qu8\"#P" }}{PARA 11 "" 1 "" {XPPMATH 20 "6% \"&nL\"\".^bDB!*>#\"$j\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$J%\".2A -$4'z)\"#V" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M47,5 ,200);pollard(M53,5,200);pollard(M59,5,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\")j+h5\"0F`N)[P29\"#Z" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"-hZyG(H\"\"1\"*4ua#*>2!*\"#`" }}{PARA 11 "" 1 "" {XPPMATH 20 "6% \"'^*z\"\"3([BMI_2Yw&\"#h" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M67,5,200);pollard(M71,5,200);pollard(M73,5,200);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$R%\"7\"RF/HRd'HtW %*\"#t" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pollard(M79,5,200 );pollard(M83,5,200);pollard(M97,5,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"%(o#\"9(3`te9t!)4HY/'\"#z" }}{PARA 11 "" 1 "" {XPPMATH 20 "6% \"$n\"\":2%\\wRLq\"pb19n*\"#$)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"&Z 9\"\"?r1!z3(=v'G&G]Kc%e\"\"#(*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "The results are the same, with the same 4 failures, and the same outc ome if we increase kmax:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "pollard(M11,5,5000);pollard(M29,5,5000);pollard(M67,5,5000);pollard(M 71,5,5000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#%&Fail1G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"*@ xq$>\"6FHTw'*e_RdZ\"\"%xE" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'z%G#\" 7ZogA[VTK=hB\"%4;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 150 "This is be cause the p-1 method is very insensitive to the choice of base a: only in \"fluke\" situations will changing a affect the result of the test ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "(c) \+ Repunits: For k=1 we get 1, so start from k=2" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "for k from 2 to 30 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "print(\"k\"= k);N:=(10^k-1)/9; pollard(N,2,50);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail1G " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\" $6\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"%66" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#6\"%66\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"&" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"&66\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#T\"&66\"\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q \"k6\"\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"'666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"'666\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \"(666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$R#\"(666\"\"#<" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\")6666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#6\" )6666\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"*6666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"*6666\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# /Q\"k6\"\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"+66666" }} {PARA 11 "" 1 "" {XPPMATH 20 "6%\"$^%\"+66666\"\"&" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#/Q\"k6\"\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"N G\",66666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"&\\;#\",66666\"\"#T" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"-666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\" $\"-666666\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#8" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\".666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"%(=%\".666666\"\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#/Q\"k6\"\"#9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"/6666666" }} {PARA 11 "" 1 "" {XPPMATH 20 "6%\"#6\"/6666666\"\"&" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#/Q\"k6\"\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"N G\"06666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"06666666\"\"\" #" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"166666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\" #<\"166666666\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#<" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"266666666\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\" \"#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"3666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"3666666666\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \"4666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"56666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"$^%\"56 666666666\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#@" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"66666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"66666666666\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#A" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \"766666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#6\"766666666666\" \"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#B" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"NG\"866666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&Fail2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#C" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"9666666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"9666666666666\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \":666666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#T\":6666666666 66\"\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#E" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\";6666666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#6\";6666666666666\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#F" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"<6666666 666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"<6666666666666\"\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#G" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"NG\"=66666666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"#6\"=66666666666666\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q \"k6\"\"#H" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\">66666666666666 \"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"%\">$\">66666666666666\"\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#I" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"?666666666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"\"$\"?666666666666666\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 96 "We fail to find a factor in the 4 cases k=2, 17, 19, 23. For k= 2, we have N=11 which is prime. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "For k=17 we can factorise N by increasing kmax:" }}{PARA 11 "" 1 " " {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "N:=(10^17 -1)/9; pollard(N,2,2000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"2 66666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(B<2#\"266666666\"\"%p 5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"+dBAj`\"\"\"-F%6#\"(B<2#F(" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "ifactor(5363222356);ifactor( 2071722);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#**)-%!G6#\"\"#F(\"\"\"-F& 6#\"#F(-F%6#\"%p5F(" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "The prime factorisation of p-1 for the two prime factors p of N shows that 1069 steps are needed." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "In the ot her two cases, the repunits are prime:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "isprime((10^19-1)/9);is prime((10^23-1)/9);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Question 5 -- Pollard's Rho Algori thm" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 229 "rho:=proc(n,c,x0,imax) lo cal x,y,i,g;x:=x0;y:=x0;\nfor i from 1 to imax do\n x:=x^2+c mod n;\n y:=y^2+c mod n; y:=y^2+c mod n;\n g:=gcd(x-y,n);\n if g=n then RET URN(Fail); fi;\n if g>1 then RETURN(g,i); fi; \nod;\nRETURN(Fail);\ne nd:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "(a) " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "n:=403; rho(n,1,1,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"$.%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\"#J\"\"$" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 23 "n:=1891;rho(n,1,1,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"%\"*=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#J\" \"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "n:=5157437;rho(n,1,1 ,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"(Pu:&" }}{PARA 11 " " 1 "" {XPPMATH 20 "6$\"%tA\"#O" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "rho(F5,1,1,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$T'\"#A " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "rho(F6,1,1,1000);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\"'xTF\"$3)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "rho(F7,1,1,10000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "rho(F7,2,3 ,50000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "We are able to factorise all the numbers in Q4 (a) except F7 (which we couldn't factorise by the p-1 method either)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "(b) Mer senne numbers (excluding the Mersenne primes)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M11,1,1,100);rho(M23,1,1,100);rho(M29,1,1,10 0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#B\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#Z\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"'Pn[\"#9 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M37,1,1,100);rho(M4 1,1,1,100);rho(M43,1,1,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$B# \"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"&nL\"\"#U" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"$J%\"#=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M47,1,1,100);rho(M53,1,1,100);rho(M59,1,1,500);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6$\"%^B\"#]" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"% hj\"#n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"'^*z\"\"$W%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "rho(M67,1,1,10000);rho(M71,1,1,500) ;rho(M73,1,1,500);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"*@xq$>\"%Gb" } }{PARA 11 "" 1 "" {XPPMATH 20 "6$\"'z%G#\"$'Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$R%\"#C" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M79,1,1,500);rho(M83,1,1,500);rho(M97,1,1,500);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"%(o#\"#\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$n \"\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"&Z9\"\"$+\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 379 "So we manage to factorise all these Mers enne numbers, although the number of iterations required is unpredicta ble (notice we need 5528 for M67). If we change either x0 or c, we get different results (the number of iterations changes, and sometimes we get a different factor). Usually the number of iterations is (very ro ughly) proportional to the square root of the factor found." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "r ho(M11,1,2,100);rho(M23,1,2,100);rho(M29,1,2,100);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"#B\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#Z\"\" )" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$L#\"#7" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 51 "rho(M37,1,2,100);rho(M41,1,2,100);rho(M43,1,2, 100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$B#\"#5" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"&nL\"\"#U" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$J% \"#=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M47,1,2,100);rh o(M53,1,2,100);rho(M59,1,2,500);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\" %^B\"#]" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"%hj\"#n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"'^*z\"\"$W%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "rho(M67,1,2,10000);rho(M71,1,2,500);rho(M73,1,2,500);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\"*@xq$>\"%Gb" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"'z%G#\"$'Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$R%\" #C" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M79,1,2,500);rho( M83,1,2,500);rho(M97,1,2,500);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"%( o#\"#\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$n\"\"\"&" }}{PARA 11 " " 1 "" {XPPMATH 20 "6$\"&Z9\"\"$+\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M 11,3,1,100);rho(M23,3,1,100);rho(M29,3,1,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#B\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#Z\"\"( " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"%.6\"\")" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 51 "rho(M37,3,1,100);rho(M41,3,1,500);rho(M43,3,1, 100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$B#\"#I" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"&nL\"\"#%)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$J% \"#A" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "rho(M47,3,1,100);rh o(M53,3,1,100);rho(M59,3,1,1000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$ \"%^B\"#A" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"%hj\"#))" }}{PARA 11 " " 1 "" {XPPMATH 20 "6$\"'^*z\"\"$m&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "rho(M67,3,1,10000);rho(M71,3,1,500);rho(M73,3,1,500); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"*@xq$>\"%>p" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"'z%G#\"#'*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$R%\" #G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "rho(M79,3,1,500);rho( M83,3,1,500);rho(M97,3,1,500);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"%( o#\"#%)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$n\"\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"&Z9\"\"$S\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "(c) repunits:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "for k from 2 to 30 d o " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "print(\"k\"= k);N:=(10^k-1)/ 9; rho(N,1,1,50);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"%66" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\" %" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"&" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"NG\"&66\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#T \"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"'666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\" \"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"(666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$R#\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"\")" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\")6666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\" \"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"*6666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q \"k6\"\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"+66666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #/Q\"k6\"\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\",66666\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"-666666 " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \".666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#z\"\"%" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"NG\"/6666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"06666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$ \"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"166666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\" #<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"266666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\" k6\"\"#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"3666666666" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \"4666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"NG\"56666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"66666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6$\"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#A" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"766666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6 \"\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"866666666666\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%FailG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"96666666 66666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" NG\":666666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#T\"\"(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#E" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\";6666666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"$p)\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#F" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"<6666666666666\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/ Q\"k6\"\"#G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"=66666666666666 " }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#H" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG \">66666666666666\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"&jn\"\"#9" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/Q\"k6\"\"#I" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"?666666666666666" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 207 "With x0=c=1 we fail to find a factor in 50 steps for the same cases as in Q4(c), \+ viz,k = 2, 17, 19, 23 and also for 11. For k=2, 19 and 23 we know that N is prime. Try changing parameters in the other cases:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "N:=(10^11-1)/9;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\",66666\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rho(N,1,1,200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\" &\\;#\"$i\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rho(N,2,3,10 0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"&\\;#\"#H" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 299 "For k=11 we get a factorisation, either by incre asing imax or changing the pseudorandom sequence. For k=17, the prime \+ factors of N are large, so we are likely to need imax large to find a \+ factorisation. The number of iterations needed may still vary dramatic ally with the particular sequence used..." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "N:=(10^17-1)/9;ifact or(N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"266666666\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"+dBAj`\"\"\"-F%6#\"(B<2#F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "rho(N,1,1,10000);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\"(B<2#\"%iG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rho(N,2,3,500);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"(B<2#\"$F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "205 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }