{VERSION 11 1 "Mac OS X" "11.1" } {USTYLETAB {PSTYLE "Ordered List 5" -1 200 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 144 2 0 2 2 -1 1 } {PSTYLE "Heading 4" -1 20 1 {CSTYLE "" -1 -1 "MS Serif" 1 12 0 0 0 1 1 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Text Output " -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 3 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 1" -1 201 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Annotation Title" -1 202 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Autho r" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 } 3 1 0 0 8 8 2 0 2 0 2 2 -1 1 }{PSTYLE "Dash Item" -1 16 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "MS Serif" 1 14 0 0 0 1 1 1 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Diag nostic" -1 9 1 {CSTYLE "" -1 -1 "Courier" 1 12 40 120 40 1 2 2 2 2 2 1 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 4" -1 203 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 108 2 0 2 2 -1 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Line Printed Output" -1 6 1 {CSTYLE "" -1 -1 "Courier " 1 12 0 0 255 1 2 2 2 2 2 1 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 } {PSTYLE "List Item" -1 14 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "MS Serif" 1 16 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 2 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 3" -1 204 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 72 2 0 2 2 -1 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier" 1 12 255 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Map le Plot" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Warning" -1 7 1 {CSTYLE " " -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "MS Serif" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 2" -1 205 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 36 2 0 2 2 -1 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 } {CSTYLE "Equation Label" -1 200 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Text" -1 201 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Page Number" -1 33 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Maple Input" -1 0 "Courier" 1 12 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Output" -1 20 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 0 0 0 1 }{CSTYLE "2D Inert Output" -1 202 "Times" 1 12 144 144 144 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Dictionary Hyperlink" -1 45 "MS Serif" 1 12 147 0 15 1 2 2 1 2 2 2 0 0 0 1 }{CSTYLE "2D Input" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 203 "Co urier" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "T imes" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Annotation Text" -1 204 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "MS Serif" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }{PSTYLE "" -1 206 1 {CSTYLE "" -1 -1 "Courier" 1 12 255 0 0 1 2 1 2 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{CSTYLE "" -1 205 "Courier" 1 16 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "update:= proc(z,a,b ) global p,g,beta; local zz,aa,bb;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " aa:=a: bb:=b:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " if z

" 0 "" {MPLTEXT 1 0 56 " elif z> 2*p/3 then zz:=z*g mod p; aa:=a+1 mod(p -1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 " else zz:=z*z mod p; aa: =2*a mod (p-1); bb:=2*b mod (p-1) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " end if:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " (zz,aa,bb) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "end proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "PollardRho:= " }{MPLTEXT 1 0 66 "pr oc(p,g,beta) local a0,b0,aX,bX,aY,bY,x,y,UB,i,dB,dA,DL,DL1,DL2;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " a0:=0; b0:=0; aX:=a0: bX:=b0:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 " aY:=a0: bY:=b0: \+ # INITIALIZATION" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " x:=g &^aX \+ * beta &^bX mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 " y:=g &^aY * beta &^bY mod p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 " UB:=2^25 : # UPPER BOUND ON NO. OF ITERATIONS" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " (x,aX,bX):=u pdate(x,aX,bX): # x - one application" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " (y,aY,bY):=update(y,aY,bY):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 " (y,aY,bY):=update(y,aY,bY): # y - two applications" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 " i:=1: # O NE ROUND OUT OF LOOP" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 " while not(x=y) and i " 0 "" {MPLTEXT 1 0 34 " (x,aX,bX):=update(x,aX, bX):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " (y,aY,bY):=update(y, aY,bY):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " (y,aY,bY):=update (y,aY,bY):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " i:=i+1:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od:" }}{PARA 206 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " print(`i=`,i) ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 " if i " 0 "" {MPLTEXT 1 0 62 " if igcdex(dB,p-1,'inv','foo')=1 then DL:=(inv*dA) mod (p-1):" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " print(" }{MPLTEXT 1 0 13 "`beta=`,beta," }{MPLTEXT 1 0 31 "`DL=`,DL,`g^DL=`,g &^DL mod p) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 " elif igcdex(dB,p-1,'inv','foo') =2 then dA:=dA/2; dB:=dB/2;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 " \+ igcdex(dB,(p-1)/2,'inv','foo');" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 " DL1:=(inv*dA) mod (p-1)/2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 " DL2:= DL1 + (p-1)/2; \+ print(" }{MPLTEXT 1 0 15 "`beta=`,beta); " } {MPLTEXT 1 0 19 "print(`gcd was 2`);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 " print(`DL1=`,DL1);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 " print( `g^DL1=`,g &^DL1 mod p ); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 " prin t(` DL2=`,DL2);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 " \+ print(`g^DL2=`,g &^DL2 mod p); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 69 " else print(`gcd was`,gcd(dB,p-1)); print(`dA=`,dA,`dB=`,dB) en d if;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "end proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "p:=971; g:=43; beta:= g &^ 285 mod p ; # INPUT VALUES g should be primitive mod p " }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 2 "Po" }{MPLTEXT 1 0 19 "llardRho(p,g,beta);" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "p:=75011: g:=49 9: beta:= g &^ 45000 mod p: " }{MPLTEXT 1 0 21 "PollardRho(p,g,beta);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "beta:= g" }{MPLTEXT 1 0 17 " &^ 45001 mod p: " }{MPLTEXT 1 0 21 "PollardRho(p,g,beta);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "beta:= g &^ 45016 mod p:" } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Pollard Rho(p,g,beta);" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 205 11 "p:=2^40-87:" }{MPLTEXT 1 0 8 " g:=13: " }{MPLTEXT 1 0 26 "beta:= g &^ 4435016 mod p:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "isprime(p);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "ifactor(p-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "Poll ardRho(p,g,beta);" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 15 10 1804 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }