{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 }{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 O utput" 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 21 "MAS3008 NUMBER THEORY" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "SOME NUMBER-THEORETIC ALGORITHMS" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "1. Binary Powering Alg orithm" }}{PARA 0 "" 0 "" {TEXT -1 34 " powerod(a,k,n) computes a^k mo d n" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "powermod:=proc(a,k,n) loc al b,c,i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "c:=a;b:=1;i:=k;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "while i>0 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " if (i mod 2=1) then b:=b*c mod n; i:=i-1;fi;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " c:=c*c mod n; i:=i/2;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "RE TURN(b);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }{TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "An example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "powermod(15,90,91);" }}}{EXCHG {PARA 11 "" 1 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "2. Miller-Rabin Primality Test." } }{PARA 0 "" 0 "" {TEXT -1 254 "spsp(n,a) returns \"Pass\" if n passes \+ the Miller-Rabin test to base a, that is, either n is prime or n is a \+ strong pseudoprime to base a. It returns \"Fail\" otherwise, in which \+ case n is composite. Where possible a non-trivial factor of n is also \+ returned." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 192 "The algorithm as given below uses the powermod subroutine of (1) \+ above. It would run slightly faster if instead we used MAPLE's built-i n implementation of the Binary Powering Algorithm, i.e. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "replace b:=powmod(a,m,n); in line 7 below by b:=a&^m mod n;" }}{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 mo d 2=0 do m:=m/2; s:=s+1 od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "b:=p owermod(a,m,n);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "if b=1 then RETU RN(Pass) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if b=n-1 then RETUR N(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)) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "if b1=n-1 then RETURN(Pass) fi;" }}{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 "" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "Some examples:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "spsp(561,1);spsp(561,561);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "spsp(56,2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "spsp(567,7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "spsp(561,2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "spsp(2047,2);" }{TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "spsp(2047,3);" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=1373653;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "spsp(n,2);spsp(n,3);spsp(n,5 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "n:=1001152801;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "spsp(n,2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 24 "3. Pollard's p- 1 method." }}{PARA 0 "" 0 "" {TEXT -1 120 "pollard(n,a,kmax) runs Poll ard's p-1 algorithm to look for a proper factor of n, starting with ba se a, up to kmax steps." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "Fail2 indicates its worth increasing kmax . Fail1 indicates that " }}{PARA 0 "" 0 "" {TEXT -1 82 "increasing kma x won't help - changing a might help, but is unlikely to in general." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "Again, \+ we use powermod from above to carry out the Binary Powering Algorithm " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "pollard:=proc(n,a0,kmax) local a,g,k;" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 6 "a:=a0;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "fo r k from 2 to kmax do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " a:=power mod(a,k,n);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " g:=gcd(a-1,n);" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " if g=n then RETURN(Fail1); fi;" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " if g>1 then RETURN(g,n,k) fi;" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "RETURN(Fail2);" }}{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 "" {TEXT -1 41 "Some exampl es (as described in lectures):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "pollard(403,2,50);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pollard(1891,2,50);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pollard(1891,3,50);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pollard(1891,5,50);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=5157437;" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "pollard(n,2,50);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "n:=2^32 +1;" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "polla rd(n,2,100);" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "pollard(n,3,100);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 25 "4. Pollard's `rho' method" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "rho(n,c,x0,imax) looks for a prop er factor of n, carrying out up to imax iterations of the rho algorith m, using the function x->x^2+c starting with the given x0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "The outpu t is either Fail, or a factor, followed by the number of step taken to find it." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 37 "rho:=proc(n,c,x0,imax) local x,y,i,g;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "x:=x0;y:=x0;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "for i from 1 to imax do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " \+ x:=x^2+c mod n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " y:=y^2+c mod n ; y:=y^2+c mod n;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " g:=gcd(x-y,n );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " if g=n then RETURN(Fail); f i;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " if g>1 then RETURN(g,i); fi ; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "RETURN(Fail);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "en d:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "We'll try it out on the same examples as above:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "rho(4 03,1,1,100);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "rho(1891,1, 1,100);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "rho(5157437,1,1, 100);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "rho(2^32+1,1,1,100 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "rho(2^64+1,1,1,100); " }}}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "rho(2^64+1,1,1,1000);" }}} {MARK "2 1 1" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }