{VERSION 4 0 "SUN SPARC SOLARIS" "4.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 } {CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{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 0 "" }{TEXT 256 19 "Factoring \+ integers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "The following algorithm tries to find a non-trivial factor of n us ing Pollard's p-1 method." }}{PARA 0 "" 0 "" {TEXT -1 55 "It does not \+ always work, the procedure may return FAIL." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "B is a bound that tells us how \+ far to search." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 250 "FACT := proc(n,B)\n loc al a,q,v,b,g;\n a := rand(2..n-2)();\n v := prime_powers(B);\n for \+ q in v do\n a:=modp(power(a,q),n);\n g:=igcd(a-1, n);\n if g<>1 then\n if g=n then return FAIL else return g fi\n fi \n od;\n FAIL\nend:\n " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 " Compute all prime powers that are less than B." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 297 "prime_powers := proc(B)\n options remember; \n local B1,v,i,j,p,k;\n B1 := floor(evalf( sqrt(B) ));\n i:=1; \+ p:=2;\n while p " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "B := 10^3:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Produce a rando m n-digit prime:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "P:=proc (n) nextprime( rand(1..10^n)() ) end;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PGR6#%\"nG6\"F(F(-%*nextprimeG6#--%%randG6#;\"\"\")\"#59$F(F (F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "P(4);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"%>z" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "P(5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"&j%>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 111 "Count := 0; for i to 100 do\n n:=P(8)*P (9);\n k:=FACT(n,B);\n if k<>FAIL then Count:=Count+1 fi;\nod:\nCo unt;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&CountG\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#@" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "Now t ry with larger B." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "B := 1 0^4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG\"&++\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 111 "Count := 0; for i to 100 do\n n :=P(8)*P(9);\n k:=FACT(n,B);\n if k<>FAIL then Count:=Count+1 fi; \nod:\nCount;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&CountG\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"#l" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "Thus, with n = (8 digit prime)*(9 digit prime) with B = 10^3 we have 21% chance of success, and with B=10^4 we have 65% chance of success." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 150 "Which is better? Well, 10^4 is 10 times bigger than 10^3 (so it can take 10 times longer) but it only gives a 3 times higher probabil ity of success." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 374 "So if there exist other equally good methods, then it wo uld be best to go with B=10^3 and if it fails, to try another method. \+ Using a 10 times faster computation (and then trying that 3 or 4 times ) is not a bad idea. But if n = p*q, then for the procedure FACT to wo rk, we need that p-1 or q-1 is B-smooth. If it isn't, then it's pointl ess to try this same procedure again.\n" }}{PARA 0 "" 0 "" {TEXT -1 29 "Lets look at what Maple does:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verboseproc=2);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 12 "op(ifactor);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6# %\"nG6%%$solG%\"rG%#t1G6%%)rememberG%'systemG%aoCopyright~(c)~1991~by~ the~University~of~Waterloo.~All~rights~reserved.GE\\s*\"-S'3er()**0)-% !G6#\"\"#\"\"(\"\"\")-F36#\"\"$F5F7-F36#\"\"&F7-F36#\"#6F7)-F36#\"#F7-F36#\"$n\"F7\"._7/-N?\"*2)F2F5F7)F9\"\"%F7)-F36#F6F5F7-F 36#\"#HF7-F36#\"#JF7-F36#\"#PF7-F36#\"#VF7-F36#\"#`F7\"-eLwt!z**(F2F7- F36#\"'()H%)F7-F36#\"'<2eF7\"-g$H*4x)**4)F2FPF7F9F7F8$F7>8%F^u2F^uFcuC$>Ffu!\"\">Fhu,$F^uF\\vOFcu-Fct6$F^ u.%)fractionGO*&-9!6$-%#opG6$F7F^u&Fft6#;F5F\\vF7-Fgv6$-Fjv6$F5F^uF\\w F\\v-Fct6$F^u<&.%$setG.%%listG.%\"*G.%)relationGO-%$mapG6%FgvF^uF\\w3- Fct6$F^u%\"^G-Fct6$FawF_uO)FfvFaw-Fct6$F^u-F36#F_uOFfvYQ2invalid~argum ents6\"@$-%)assignedG6#&%7ifactor/from_signatureG6#FhuOFfy>8&-%%igcdG6 $Fhu\"'?2s?(6\"F7F7Faz0F[zF7C%>Ffu*&FfuF7-%1ifactor/ifact235G6#F[zF7>F hu-%%iquoG6$FhuF[z>F[z-F]z6$F[zFhu>F[z-F]z6$Fhu\"igmL#4(*G]KKT_/&o:-6- \\ULnO63K//a2+Jg1(yv%))=%>78\">_=)RBQ#>VWyw'G*R%G\\?$f7!e@ZzI(*yye56c \"y)**o*)QLhqw-?=(zuT%e<6)fZ@Q*[2)3#>wd'*\\:G(*)z=]^VV.h9MkueL(z![$)** Hq1x_w')Rd#QeVva%>VJ\"))ez>!*He%\\xPDRmf-60&3OlWa]rHz(zX$[VqF@7Hs,A!zA nr6'>C%\\$fw>r,cG\"31+7sAdQ@A(zC>XzNl(*4)\\0aFc@**)y;u2(R&)H\\..*H7\"y V-VoEZ>IAzQ%H3>#=%y%))*Q?>l?')f!pq1Vkpj(4R=cVxQ,'o1aK,npXBR,W[tUA)H'4- FhUPX3y&*3(>b')GHWsiV[_.pt5=bqyi!=TRbUc#=@W,P9^Ha;\"?(FazF7F7FazFbzC%> Ffu*&FfuF7-%1ifactor/ifact1stGFhzF7>FhuFjz>F[zF^[l@%0FhuF7C$@%/F[tF7@% 3/%2_Env_ifactor_easyG%%trueG2\"#I-%'lengthGFhyC$>%/ifactor/bottomG%-i factor/easyG>F[z-%1ifactor/ifact0thGFhyC$>F\\]l%1ifactor/morrbrilG>F[z F_]lC$>F\\]l-%$catG6$%)ifactor/GFet>F[z-F`]l6$Fhu&Fft6#;F;F[t@%0F[z%%F AILG*&FfuF7F[zF7Fc^lFfuFaz6#F\\]lFaz" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "op(`ifactor/ifact0th`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6#%\"nG6$%$solG%\"pG6#%aoCopyright~(c)~1991~by~the~University~o f~Waterloo.~All~rights~reserved.G6\"C,@$29$\"(\"o?HO-%!G6#F/@$-%(ispri meGF4OF2>8$-%.ifactor/powerG6$F/.8%@$0F:%%FAILGO)-%1ifactor/ifact0thG6 #F:F?>F:-%/ifactor/pollp1G6$F/\"&.I\"@$/F:%*_tryagainG>F:-FJ6$F/\"&/I \"@$FN>F:FB@$/F:FB>F:-%1ifactor/pp100000GF4@$FWC$>F:-%/ifactor/bottomG 6#9\"@$4-%%typeG6$F:.%(integerGOF:*&-FF6$*&F/\"\"\"F:!\"\"&F[o6#;\"\"# 9#Fho-FF6$F:FjoFhoF+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "op(`ifactor/pollp1`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6$%\"nG%%se edG6(%'primesG%\"wG%\"iG%#t1G%\"dG%%pairG6#%aoCopyright~(c)~1990~by~th e~University~of~Waterloo.~All~rights~reserved.G6\"C&>8$7V\"$7&\"+D1S,F \",(*3Dp`\"\"/6y%eA>?#\".x8FEAJ$\"-8lv!Qt&\".P>V:f*)*\".P\\9K5!**\"/80 7M$en#\"0fit_cM@#\"0rjGNj*=N\"0P2lTF`-'\"0pNY8e!fq\"1rJad-'o9\"\"1>w;Q M#z>\"\"1`3NAG=,T\"2H!*[p@j$4=\"2*>\\BLTty:\"28T$o`)pT0$\"2xFV5b'GFK\" 2*G[fQBK>!*\"2$f>Bjz#f[*\"3H%[H%p&y&4A\"3$*\\Gf*znU<#\"3@2>\"=A&=QN\"3 *[%)GYX**R>%\"3dMJn!*=Wsd\"3B7w-)[kcw&\"38ej;$R/,N'\"4H1$Rd1'3K;\"\"4` JrgKaFXF\"\"3xY'GW$[,U'*\"4\")>%3ca!\\&*=\"\"4LNqO#H5mI<\"4hP!3'o*f_CB \"4Zl(*=\\2z$\\<\"4hZZ'=)4=$zB\"4j=-Ni+5j!R\"4LkaoH$p.+W\"4T=HP@(yN'[$ \"428JID&3b^S\"48Hb8>?CH1(\"4d'Gn*yQ/i%**\"4@S#3!G$*>/!)*\"5J:KQJX;k,9 \"5t-*[jcqa^%=\"5HN!oH\">R3x?\"5*)e[!)Q(yBiK#\"5p(G%y_YAHGG\"5V9q;)H+U zP#\"5.+A/+OFk+H\"8\\#HkoRH87%HK'>8%9%?(8&\"\"\"Fho-%%nopsG6#F3%%trueG C$>8'-%%modpG6$-%&powerG6$Fdo&F36#Fgo9$@%0-%%igcdG6$,&F_pFhoFho!\"\"Fh pFhoC&@$0F_pFho-%'RETURNG6#F[q>8(-%#opG6$\"\"#-%)ifactorsG6#Ffp?&8)Fgq F\\p?(F0FhoFho&F`r6#F[rF\\pC$>Fdo-Fap6$-Fdp6$Fdo&F`r6#FhoFhp@&/FdoFho@ $2FhoFgo-Fdq6#-9!6$Fhp-Fap6$-Fdp6$FeoFjrFhp0-F\\q6$,&FdoFhoFhoF_qFhpFh o-Fdq6#Fjs-Fdq6#%*_tryagainG>FdoF_p%%FAILGF0F0F0" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 68 "This last procedure is Maple's implementation of P ollard p-1 method." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 207 "The list of numbers are products of primes, all of which are <2000. So Maple applies an algorithm similar to FACT above, wher e B is in essence equal to 2000. If that fails, then other algorithms are tried." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "A particularly interesting algorithm is Lenstra's elliptic curv e algorithm:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "op(`ifactor /lenstra`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6#%\"nG61%\"iG%\"sG%&p rimeG%\"fG%\"AG%\"XG%\"ZG%%rgenG%#spG%\"aG%\"rG%'curvesG%#B1G%#kgG%$kg gG6#%aoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~rights~re served.G6\"C0@$529#\"\"\"2\"\"$F=YQ;wrong~number~of~arguments.6\"@%2F= F@>80\"(+++\">FG&9\"6#F@@%2F=\"\"#>8/\"#I>FQ&FK6#FO@$/-%%modpG6$9$FO\" \"!-%'RETURNGFU@$/-FY6$FenF@Ffn-FhnFL>8%-%&evalfG6$,&-%%sqrtG6#\"\"&#F >FO#F>FO!\"\"FR>8(-%&arrayG6#;F>FQ>8)F]p>8*-F^p6$F`p7#-%\"$G6$F>FQ>8+- %%randG6#;F>,&FenF>F>Fjo?(8$F>F>FQ%%trueGC&>8-Ffn?(F8F>F>F8/-FY6$*(Fgq F>,&*$)FgqFOF>F>F>FjoF>,&F^r\"\"*F>FjoF>FenFfnC'>8.-F\\qF8>81,&*$)FdrF OF>F>\"\"'F>>82-%%igcdG6$FgrFen@$0F]sF>-Fhn6#F]s>Fgq-FY6$,$*&FdrF>FgrF joF[sFen>&F\\p6#Fcq-FY6$,&*&,(*$)Fgq\"\"%F>!\"$*&F[sF>F_rF>FjoF>F>F>*$ )FgqF@F>Fjo#F>\"#;FhoF>Fen>&FbpF\\t-FY6$,$Fgq#F@FdtFen>8&FO?(F8F>F>F81 FbuFGC)>8,-%&roundG6#*&F_oF>FbuF>-%6ifactor/lenstra/mulppG6*F>FenF\\pF guFbuFGFbpFdp>8'&Fdp6#F>?(FcqFOF>FQFdqC$-F]v6*FcqFenF\\pFguFbuFGFbpFdp >F`v-FY6$*&F`vF>&FdpF\\tF>Fen>F`v-F_s6$F`vFen@$0F`vF>-Fhn6#F`v>Fbu-%*n extprimeG6#Fbu%%FAILGF8F8F8" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 378 "W e see that Maple's implentation tries 30 curves. That's like running p rocedure FACT thirty times, however, each time with a different groupo rders (in FACT the group orders are always p-1 and q-1, so it is point less to try FACT more than once). But with random elliptic curves, eac h time you try you get a different unknown grouporder, so each time yo u try you get a new chance." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "To see yet another factoring algorithm, type:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "op(`ifactor/pollard`);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#R6$%\"nG%#exG6&%#EXG%%rho1G%%rho2G%+i gcd_rho12G6#%aoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~r ights~reserved.G6\"C'@'/9#\"\"\">8$\"\"#550F2F64-%%typeG6$9%%(integerG 2F>F6YQ2invalid~arguments6\">F5F>>8%F6>8&-%%modpG6$,&-.%&powerG6$F6F5F 3F3F39$?(F.F3F3F.%%trueGC&>FF-FJ6$,&-FN6$FFF5F3F3F3FQ>FH-FJ6$,&-FN6$,& -FN6$FHF5F3F3F3F5F3F3F3FQ>8'-%%igcdG6$,&FFF3FH!\"\"FQ@$2F3F_o@%/F_oFQO %%FAILGOF_oFjoF.F.F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "This last algorithm is called Pollard's rho algorithm." }}}}{MARK "0 0 1" 19 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }