{VERSION 6 0 "SUN SPARC SOLARIS" "6.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 81 "Definition. Let B be a positive integer. Then an integer n is cal led B-smooth if" }}{PARA 0 "" 0 "" {TEXT -1 48 "every prime-power that divides n is less than B." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "If B is a number that is not very large, then eve ry B-smooth integer is easy to factor" }}{PARA 0 "" 0 "" {TEXT -1 85 " (just try all primes less than B). Maple's ifactor command contains \+ lists of primes" }}{PARA 0 "" 0 "" {TEXT -1 84 "below 100000, so ever y 100000-smooth integer will be very easy to factor for Maple." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "Thus, in \+ the problem of integer factorization, we might as well assume that the " }}{PARA 0 "" 0 "" {TEXT -1 77 "number n that we want to factor conta ins no primes that are less than 100000." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "If n is prime then this can be det ected quickly using the probabilistic algorithm" }}{PARA 0 "" 0 "" {TEXT -1 74 "isprime (basically, Maple isprime command tests if Fermat 's little theorem" }}{PARA 0 "" 0 "" {TEXT -1 63 "(that a^p congruent \+ to a mod p) holds for about two dozen a's)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "If n is a prime-power, that too is easy to detect." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 66 "After treating the easy cases, we can assume that n = p * q * ...." }}{PARA 0 "" 0 "" {TEXT -1 66 "(i.e. n contains at least \+ two primes p, q and perhaps more primes)" }}{PARA 0 "" 0 "" {TEXT -1 71 "and can also assume that every prime factor of n is larger than 10 0000." }}{PARA 0 "" 0 "" {TEXT -1 26 "So n is not 100000-smooth." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "Then the \+ next easiest case is when for at least one of the prime factors p of n " }}{PARA 0 "" 0 "" {TEXT -1 75 "the number p-1 is B-smooth, for some \+ number B that is not too big (Maple's" }}{PARA 0 "" 0 "" {TEXT -1 74 "implementation uses B=2000 in this case, so if n contains a prime num ber p" }}{PARA 0 "" 0 "" {TEXT -1 67 "for which p-1 is 2000-smooth, th en we're in the next easiest case)." }}{PARA 0 "" 0 "" {TEXT -1 67 "Th is case is treated with an algorithm called Pollard's p-1 method." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "The follo wing algorithm tries to find a non-trivial factor of n using 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 sea rch." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 250 "FACT := proc(n,B)\n local 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 the n\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 a ll prime powers that are less than B." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 297 "prime_powers := proc(B)\n options remember;\n lo cal 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 random n-digit prime:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "P:=proc(n) next prime( rand(1..10^n)() ) end;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"PGj+6#%\"nG6\"F(F(-%*nextprimeG6#--%%randG6#;\"\"\")\"#59$F(F(F(F(6# \"\"!" }}}{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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "op (ifactor);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "op(`ifactor/i fact0th`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "op(`ifactor/p ollp1`);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 68 "This last procedure i s Maple's implementation of Pollard 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 algor ithm similar to FACT above, where B is in essence equal to 2000. If t hat fails, then other algorithms are tried." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "A particularly interesting algo rithm is Lenstra's elliptic curve algorithm:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "op(`ifactor/lenstra`):" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 378 "We see that Maple's implentation tries 30 curves. That 's like running procedure FACT thirty times, however, each time with a different grouporders (in FACT the group orders are always p-1 and q- 1, so it is pointless to try FACT more than once). But with random ell iptic curves, each time you try you get a different unknown grouporder , so each time you try you get a new chance." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "To see yet another factoring al gorithm, type:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "op(`ifact or/pollard`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "This last algorithm is called Poll ard's rho algorithm." }}}}{MARK "0 1 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }