{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "" -1 18 "" 0 1 198 0 3 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" 18 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 0 12 0 0 128 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 96 0 0 0 0 0 0 0 2 0 0 }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 13 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 97 99 99 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "# p-1.ms\n" }{TEXT -1 722 "## Is 2^p-1 prime for infinitely many p? ##\n# Is 2^(2 ^n)+1 prime for some n > 4? #\n# \+ #\n# John B. Cosgrave, #\n# \+ Department of Mathematics, #\n# St. Patrick's Co llege, #\n# Drumcondra, # \n# Dublin 9, #\n# IRELAND. #\n# \+ #\n# Home e-mail: johnbcos@iol.ie #\n# College e -mail: John.Cosgrave@spd.ie #\n# \+ #\n# 2^sqrt(2) is transcendental. Pi(x)~x/ln(x). # \n## \+ .12345678910111213 ... is normal. Is Pi? ##\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "These notes are about John Pollard's 'p - 1' factori ng " }}{PARA 0 "" 0 "" {TEXT -1 54 "method (which was first published \+ in the 'Proceedings " }}{PARA 0 "" 0 "" {TEXT -1 50 "of the Cambridge \+ Philosophical Society', in 1974)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 59 "I should let out immediately that the 'p \+ - 1' of Pollard's " }}{PARA 0 "" 0 "" {TEXT -1 60 "'p - 1' factoring m ethod is directly related to the 'p - 1' " }}{PARA 0 "" 0 "" {TEXT -1 60 "of Fermat's 'little' theorem [Let 'p' be prime, and let 'a' " }} {PARA 0 "" 0 "" {TEXT -1 46 "be any integer such that a <> 0 (mod p), \+ then " }}{PARA 0 "" 0 "" {TEXT -1 23 "a^(p - 1) = 1 (mod p)]." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "John Poll ard is a brilliant English mathematician " }}{PARA 0 "" 0 "" {TEXT -1 55 "(he lives just outside Reading), who has created three " }}{PARA 0 "" 0 "" {TEXT -1 51 "incredible factoring methods since the mid-1970 's: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 42 "1 . the 'p - 1' method [dating from 1974]," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "2. The 'Monte-Carlo' method [dati ng from 1975] (also " }}{PARA 0 "" 0 "" {TEXT -1 36 " known as the 'rho' method), and" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 55 "3. the very, very advanced 'Number Field Sieve' (NFS) \+ " }}{PARA 0 "" 0 "" {TEXT -1 61 " method [dating from 1988]. Thi s is currently the most " }}{PARA 0 "" 0 "" {TEXT -1 66 " effectiv e practical method for factoring, setting all recent " }}{PARA 0 "" 0 "" {TEXT -1 61 " factoring 'records'. [In 1994 the famous 'RSA_12 9' was " }}{PARA 0 "" 0 "" {TEXT -1 65 " factored using a very adv anced method called the 'quadratic " }}{PARA 0 "" 0 "" {TEXT -1 61 " \+ sieve' (due to the U.S. mathematician, Carl Pomerance), " }}{PARA 0 "" 0 "" {TEXT -1 64 " and it was later factored using the NFS met hod. Since then, " }}{PARA 0 "" 0 "" {TEXT -1 52 " the NFS method h as factored an RSA_130 number. " }}{PARA 0 "" 0 "" {TEXT -1 60 " N FS has also factored other larger non-RSA type numbers " }}{PARA 0 "" 0 "" {TEXT -1 58 " whose factorisations had been long standing prob lems.]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "You will study the first two of these methods." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "Suppose one has a composi te integer ('n', let's say), which " }}{PARA 0 "" 0 "" {TEXT -1 57 "ha s been shown to be composite by - perhaps - failing to " }}{PARA 0 "" 0 "" {TEXT -1 59 "'pass a Fermat test'; can one find a 'proper' factor of n? " }}{PARA 0 "" 0 "" {TEXT -1 57 "That is, can one find a factor of 'n' other than 1 and n?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Pollard's 'p - 1' method does NOT gaurantee a s uccesful " }}{PARA 0 "" 0 "" {TEXT -1 54 "factoring of a composite int eger, but it CAN be quite " }}{PARA 0 "" 0 "" {TEXT -1 58 "useful (wit h a bit of luck). Basically Pollard's 'p - 1' " }}{PARA 0 "" 0 "" {TEXT -1 16 "method works IF:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 55 "'n' has a prime factor 'p' (which may be \+ QUITE LARGE), " }}{PARA 0 "" 0 "" {TEXT -1 55 "for which (p - 1) has o nly got 'SMALL' prime factors. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 56 "Examples. The 'Euclidean prime' 2*3*5*7* \+ ... *29*31 + 1 " }}{PARA 0 "" 0 "" {TEXT -1 53 "is such a prime; so to o is the (made up by me) prime " }}{PARA 0 "" 0 "" {TEXT -1 24 "2^21*3 ^20*5^20*7^20 + 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "IN A NUTSHELL, Pollard's (p - 1) method (AND his " }} {PARA 0 "" 0 "" {TEXT -1 49 "'Monte-Carlo' one) has this CENTRAL IDEA \+ in it: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "one has a composite number 'n' and one then ATTEMPTS " }}{PARA 0 " " 0 "" {TEXT -1 57 "to find a proper factor ot it by finding another n atural " }}{PARA 0 "" 0 "" {TEXT -1 57 "number 'M' (think of 'M' as be ing for 'magic') such that " }}{PARA 0 "" 0 "" {TEXT -1 42 "the greate st common divisor of M and n is:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 54 "[A]. GREATER that 1 (EASY!! Any M = n, 2* n, ... would " }}{PARA 0 "" 0 "" {TEXT -1 68 " \+ do, BUT uselessly!!), " }}{PARA 0 "" 0 "" {TEXT -1 59 "[B]. BUT LESS than n (that, of course, is the HARD part!!)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "[One shou ld understand that there is no PRECISE " }}{PARA 0 "" 0 "" {TEXT -1 59 "definition of 'SMALL' in this context. 'Small' means, ... " }} {PARA 0 "" 0 "" {TEXT -1 59 "well, small!! 2, 3, 5, 7, 11, 13, ... wo uld be considered " }}{PARA 0 "" 0 "" {TEXT -1 56 "'small', BUT some 8 4-digit (let us say) prime would NOT " }}{PARA 0 "" 0 "" {TEXT -1 28 " be considered 'small' ... .]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Pollard's device for creating such an elusive ' M' is to " }}{PARA 0 "" 0 "" {TEXT -1 63 "create a sequence of integer s a[1], a[2], a[3], ... which have " }}{PARA 0 "" 0 "" {TEXT -1 54 "a \+ built-in guarantee that EVENTUALLY one of them will " }}{PARA 0 "" 0 " " {TEXT -1 56 "satisfy [A] above, and for which one HOPES that it will " }}{PARA 0 "" 0 "" {TEXT -1 17 "also satisfy [B]." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "To get you started on P ollard's (p - 1) factoring method " }}{PARA 0 "" 0 "" {TEXT -1 56 "I h ave chosen a value of 'n' off the top of my head [do " }}{PARA 0 "" 0 "" {TEXT -1 19 "you believe that?]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "n := 155629;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"'Hc:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Is it prime/composite? Let's try a Fermat test to base 2 :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "2&^(n - 1) mod n; # NOTE the \+ use of the '&' before the '^'." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"': l5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 51 "The remainder is NOT 1, and so 155629 is COMPOSITE " }}{PARA 0 "" 0 "" {TEXT -1 47 "as it has 'failed Fermat's test to t he base 2'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "I will now show you HOW a factor of 'n' can be found by " }} {PARA 0 "" 0 "" {TEXT -1 57 "Pollard's (p - 1) factoring method. The IDEA is this: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "IF (and it's a BIG 'IF') 'n' has a prime factor 'p' for w hich " }}{PARA 0 "" 0 "" {TEXT -1 52 "(p - 1) has ONLY got SMALL prime factors THEN there " }}{PARA 0 "" 0 "" {TEXT -1 52 "is a fairly GOOD \+ CHANCE of finding it by doing this:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 56 "First, form the following numbers [these are essentially" }}{PARA 0 "" 0 "" {TEXT -1 36 "the numbers a[1], a[2 ], a[3], ... ]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "2^(k!) - 1; " }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,&)\"\"#-%*factorialG6#%\"kG\"\"\"!\" \"F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "with 'k' starting at 1, and at each stage calcula te the gcd " }}{PARA 0 "" 0 "" {TEXT -1 58 "of (2^(k!) - 1) and n. [L ater we will see that there are " }}{PARA 0 "" 0 "" {TEXT -1 60 "times when the '2' needs to be replaced by a '3', and ... .]" }}{PARA 0 "" 0 "" {TEXT -1 55 "So, e.g., with the above 'n' (=155629), he suggests \+ we " }}{PARA 0 "" 0 "" {TEXT -1 10 "calculate:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "[k=1:] gcd(1, 155629)," }}{PARA 0 "" 0 "" {TEXT -1 23 "[k=2:] gcd(3, 155629)," }}{PARA 0 "" 0 "" {TEXT -1 24 "[k=3:] gcd(63, 155629)," }}{PARA 0 "" 0 "" {TEXT -1 30 "[k=4:] gcd(16777215, 155629)," }}{PARA 0 "" 0 "" {TEXT -1 59 " [k=5:] gcd(1329227995784915872903807060280344575, 155629)," }}{PARA 0 "" 0 "" {TEXT -1 13 " etc." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "QUESTION: That might appear a strange t hing to do, " }}{PARA 0 "" 0 "" {TEXT -1 59 " so WHY does \+ Pollard suggest that we do this? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 41 "ANSWER: Well, Pollard argues as follows: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "1. B ecause 'n' is composite then it has SOME proper " }}{PARA 0 "" 0 "" {TEXT -1 63 " factor 'p' which is prime, and then, by Fermat's 'li ttle' " }}{PARA 0 "" 0 "" {TEXT -1 57 " theorem we will have 2^(p \+ - 1) = 1 (mod p). [We can " }}{PARA 0 "" 0 "" {TEXT -1 53 " use '2 ' because with 'n' being odd, then 'p' is " }}{PARA 0 "" 0 "" {TEXT -1 49 " automatically odd, and so doesn't divide 2.]" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "2. Once 'k' is LA RGE enough we will automatically have " }}{PARA 0 "" 0 "" {TEXT -1 66 " that (p - 1) will divide k! [Advice: do some drill examples " } }{PARA 0 "" 0 "" {TEXT -1 64 " along the following lines: For a \+ given value of 'p', how " }}{PARA 0 "" 0 "" {TEXT -1 59 " big does 'k' have to be to gaurantee that (p - 1) will" }}{PARA 0 "" 0 "" {TEXT -1 63 " divide (k!)? See the elementary worksheet 'divid_k! .ms'.]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "3. It follows that once 'k' is BIG ENOUGH then we will " }}{PARA 0 " " 0 "" {TEXT -1 58 " have 2^(k!) = 1 (mod p). That's because ONCE 'k' is " }}{PARA 0 "" 0 "" {TEXT -1 59 " BIG ENOUGH then (p - 1) \+ divides k! (see the elementary" }}{PARA 0 "" 0 "" {TEXT -1 62 " wo rksheet 'divid_k!.ms), and so k! = (p - 1)*K, for some " }}{PARA 0 "" 0 "" {TEXT -1 49 " natural number K, and then from we will have" } }{PARA 0 "" 0 "" {TEXT -1 58 " 2^(p - 1) = 1 (mod p) one will get \+ - by raising both " }}{PARA 0 "" 0 "" {TEXT -1 36 " sides to the p ower of K - that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 " (2^(p - 1))^K = 1^K (mod p)," }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 " whic h gives:" }}{PARA 0 "" 0 "" {TEXT -1 49 " \+ 2^(k!) = 1 (mod p), " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 50 " and THUS (2^(k!) - 1) WILL BE divisible by p." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "4. n, ho wever, is ALREADY divisible by p, and so the gcd " }}{PARA 0 "" 0 "" {TEXT -1 56 " of 2^(k!) - 1 AND n will be GREATER than 1 (that's \+ " }}{PARA 0 "" 0 "" {TEXT -1 56 " condition [A] above), AND, with \+ a bit of LUCK that " }}{PARA 0 "" 0 "" {TEXT -1 53 " gcd WON'T be \+ 'n', but be SMALLER than n (that's " }}{PARA 0 "" 0 "" {TEXT -1 58 " \+ condition [B] above), and so be a PROPER FACTOR of n." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "[Of course, all of this would be USELESS were it not for " }}{PARA 0 "" 0 "" {TEXT -1 56 "the fact that gcd's and 'modular exponentiation' can be " }}{PARA 0 "" 0 "" {TEXT -1 55 "calculated incredibly quickly. See other works heets - " }}{PARA 0 "" 0 "" {TEXT -1 45 "'fast_gcd.ms' and 'mod_expo.m s' - for those.]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "To get a feel for this, let us follow Pollard's suggestio n" }}{PARA 0 "" 0 "" {TEXT -1 54 "for the above value of 'n' (155629), and to give you a" }}{PARA 0 "" 0 "" {TEXT -1 54 "feeling for what is going on I will not take advantage" }}{PARA 0 "" 0 "" {TEXT -1 38 "of modular exponentiation until later:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "igcd(2^(1!) - 1, 155629); # k = 1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "and so there is NO integer greater than 1 which divides " }}{PARA 0 "" 0 "" {TEXT -1 54 "BOTH (2^(1!) - 1) and \+ 155629. That's not a surprise, " }}{PARA 0 "" 0 "" {TEXT -1 21 "since 2^(1!) - 1 = 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "Now we move on to:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " igcd(3, 155629); # k = 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "igcd(63, 155629); # k = 3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "igcd(16777215, 155629); # k = 4" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "igcd(1329227995784915872903807060280344575, 155629); # k = 5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "next_nu mber := 2^(6!) - 1; # k = 6" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,nex t_numberG\"dxv07#p)4KFfjaex:J(e;?U$*H#*zr<;'[E79m1^4]6Je>Bto6>kqk;3$fL ^N*[yLye3Q%>+g'G,#e@Cu)))>;iRps*GN7^34J63cz84V2#G(G()H()>5jAl:b" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "igcd(next_number, 155629); \+ # k = 6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#>" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "WOW!!! That MEANS that 19 is a factor of (2^(6!) - 1) " }}{PARA 0 "" 0 "" {TEXT -1 55 "AND n, and, in particular, it means that we have found " }}{PARA 0 "" 0 "" {TEXT -1 40 "a PROPER FACTOR (19) of n. FANTASTIC!! !" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "[Ant icipating a reasonable] OBJECTION: Isn't this an" }}{PARA 0 "" 0 "" {TEXT -1 56 "awful lot of work just to discover that 155629 has 19 as " }}{PARA 0 "" 0 "" {TEXT -1 50 "a proper factor? Wouldn't it have be en MUCH, MUCH" }}{PARA 0 "" 0 "" {TEXT -1 54 "EASIER just to have done the classical trial-and-error" }}{PARA 0 "" 0 "" {TEXT -1 52 "checkin g possible (prime) factors one after another:" }}{PARA 0 "" 0 "" {TEXT -1 55 "(2), 3, 5, 7, 11, 13, 17, 19, [at which point a factor " }}{PARA 0 "" 0 "" {TEXT -1 23 "would have been found]?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "REPLY: Yes, of cour se it's true that in the specific " }}{PARA 0 "" 0 "" {TEXT -1 54 "exa mple that I gave (n = 155629), the factor 19 would " }}{PARA 0 "" 0 " " {TEXT -1 51 "have been more speedily found just by brute force, " }} {PARA 0 "" 0 "" {TEXT -1 46 "BUT - and here's the CRUNCH - the same is NOT " }}{PARA 0 "" 0 "" {TEXT -1 51 "true of much larger numbers 'n' \+ having much larger " }}{PARA 0 "" 0 "" {TEXT -1 56 "prime factors. Th is point will only become appreciated " }}{PARA 0 "" 0 "" {TEXT -1 24 "later in this worksheet." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 54 "The start of real PROGRESS. In the above calculat ions" }}{PARA 0 "" 0 "" {TEXT -1 54 "I deliberately used ACTUAL values of (2^(k!) - 1), and" }}{PARA 0 "" 0 "" {TEXT -1 53 "as you see (and \+ know) they get to be huge, even with " }}{PARA 0 "" 0 "" {TEXT -1 55 " 'k' only getting up as far as '6'. But '6' is NOTHING " }}{PARA 0 "" 0 "" {TEXT -1 55 "in comparison to the sort of values we will be deali ng " }}{PARA 0 "" 0 "" {TEXT -1 56 "with in much more serious settings . We will be looking " }}{PARA 0 "" 0 "" {TEXT -1 57 "at cases in whi ch if one were using only brute force (the" }}{PARA 0 "" 0 "" {TEXT -1 54 "classical Eratosthenes checking up to the square-root)" }} {PARA 0 "" 0 "" {TEXT -1 55 "one would only find a factor after billio ns of billions" }}{PARA 0 "" 0 "" {TEXT -1 51 "of years, BUT the Polla rd method will find a factor" }}{PARA 0 "" 0 "" {TEXT -1 19 "in a few \+ seconds!!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "The two MAIN mathematical points we bring to our " }}{PARA 0 " " 0 "" {TEXT -1 41 "aid to GREATLY REDUCE the MASSIVE amount " }} {PARA 0 "" 0 "" {TEXT -1 25 "of computation are these:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "ONE [TWO, below, is 'modular exponentiation] " }}{PARA 0 "" 0 "" {TEXT -1 54 " \+ is what I would call the 'main step of the " }}{PARA 0 "" 0 "" {TEXT -1 40 " Euclidean algorithm', namely:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "If a, b, q and r are inte gers with a = b*q + r, then" }}{PARA 0 "" 0 "" {TEXT -1 25 " \+ " }}{PARA 0 "" 0 "" {TEXT -1 39 " gcd( a, b) = gcd(b, r)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "from which we garner that with:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 " 'a' = 2^(k!) - 1 and \+ 'b' = n, we have" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 " gcd(2^(k!) - 1, n) = gcd(n, r)," }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "and, what is 'r'? \+ Well it is simply the remainder that" }}{PARA 0 "" 0 "" {TEXT -1 57 " 'a' leaves on division by 'b' (that is, it is 'a mod b', " }}{PARA 0 " " 0 "" {TEXT -1 48 "which in the above setting is 2^(k!) - 1 mod n)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "Thus we have the VITALLY IMPORTANT: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 51 " gcd(2^(k!) - 1, n) = gcd(n, 2^(k!) \+ - 1 mod n)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "The EFFECT of that is that instead of working with " }}{PARA 0 "" 0 "" {TEXT -1 48 "MASSIVE numbers like those above, we are instead " }}{PARA 0 "" 0 "" {TEXT -1 36 "ONLY working with much smaller ones: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "next_number mod 155629;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"'9l5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "igcd(155629, 106514); # as above" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"#>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "We now cut out all this hand cal culation and write " }}{PARA 0 "" 0 "" {TEXT -1 52 "a simple programme using 'while', which I will then " }}{PARA 0 "" 0 "" {TEXT -1 48 "fur ther simplify, and then convert to a GENERAL " }}{PARA 0 "" 0 "" {TEXT -1 10 "procedure." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Simple programme #1." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "for k while" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "igcd(155629, 2^(k!) - 1 mod 155629) = 1 " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "d o k od; k;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "print(igcd(15 5629, 2^(k!) - 1 mod 155629)); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\" \"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"%" }} {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 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "You a re familiar with this sort ot thing: the '1' to '5' " }}{PARA 0 "" 0 " " {TEXT -1 55 "correspond to the gcd's being '1, the '6' to the first \+ " }}{PARA 0 "" 0 "" {TEXT -1 53 "instance where the gcd is NOT 1, and \+ the '19' is the " }}{PARA 0 "" 0 "" {TEXT -1 45 "value of igcd(155629, 2^(6!) - 1 mod 155629)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 50 "We can get rid of all the distracting, irrelevant \+ " }}{PARA 0 "" 0 "" {TEXT -1 53 "output (the 1, 2, 3, 4 and 5), and al so the '6', and " }}{PARA 0 "" 0 "" {TEXT -1 51 "choose a nice 'lprint ' line with this minor change:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 20 "Simple programme #2." }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 54 "for k while igcd(155629, 2^(k!) - 1 mod 155629) = 1 " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "do k od:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 69 "lprint(igcd(155629, 2^(k!) - 1 mod 155629),` is a factor of`, 155629);" }}{PARA 2 "" 1 "" {TEXT -1 30 "19 is a fa ctor of 155629\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "and the other main mathematical t echnique which" }}{PARA 0 "" 0 "" {TEXT -1 48 "comes to our rescue is \+ 'modular exponentiation'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 42 "We REALLY MUST use modular exponentiation," }} {PARA 0 "" 0 "" {TEXT -1 55 "otherwise we will find ourselves in sever e difficulties" }}{PARA 0 "" 0 "" {TEXT -1 50 "whenever 'k' gets to be large. For example, look " }}{PARA 0 "" 0 "" {TEXT -1 50 "what happe ns if we tried to find a factor - using " }}{PARA 0 "" 0 "" {TEXT -1 49 "Pollard's idea - of the following made-up number:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "prime_1 := nextp rime(8765);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(prime_1G\"%z()" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "prime_2 := nextprime(34567); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(prime_2G\"&$eM" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "made_up := prime_1*prime_2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(made_upG\"*dTg.$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "# for k while igcd(made_up, 2^(k!) - 1 mod made_up) = 1 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "# do k od:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "# lprint(igcd(made_up, 2^(k!) - 1 mod made_up)," }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "# \+ `is a factor of`, made_up);" }}{PARA 2 "" 1 "" {TEXT -1 49 "Erro r, object too large\nError, object too large\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "I hav e put in the '#' to prevent later re-execution, " }}{PARA 0 "" 0 "" {TEXT -1 53 "and possible loss of work in the event of forgetting " }} {PARA 0 "" 0 "" {TEXT -1 25 "to save before execution." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "But now see that we \+ get instant output with the" }}{PARA 0 "" 0 "" {TEXT -1 30 "use of mod ular exponentiation:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "for k while igcd(made_up, 2&^(k!) - 1 mod made_up) = 1 " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "do k od:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "lprint(igcd(made_up, 2&^(k!) - 1 mod made_up),`is a factor of`, made_ up);" }}{PARA 2 "" 1 "" {TEXT -1 35 "8779 is a factor of 303604157 \n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "But even with that speed, we should avoid using \+ " }}{PARA 0 "" 0 "" {TEXT -1 43 "the following apparently perfect proc edure:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "seems_good_Pollard := pro c(n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local k;" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 45 "for k while igcd(n, 2&^(k!) - 1 mod n) = 1 " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "do k od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "lprint(igcd(n, 2&^(k!) - 1 mod n),`is a factor of`, n );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "se ems_good_Pollard(made_up);" }}{PARA 2 "" 1 "" {TEXT -1 35 "8779 is a factor of 303604157\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "p77 := 77! + 1; # a well known prime" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$p77G\"]r,+++++ +++[7'y?l+3?k:\\8*>1)ou:yY)e$3UAz.u$)\\G3j3%yqSjpeGG?4$=X\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "length(p77);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$9\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "and a made up one:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "q1 := nextprime(10^116 + 987654321) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#q1G\"`rVXl()4+++++++++++++++++ ++++++++++++++++++++++++++++++++++++\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(q1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$<\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 31 "n1 := p77*q1; # has 230 digits" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#>%#n1G\"ayVXl()4++++k'\\3!4S!GEGp4v.@;iL#e$pJ1)f $>,ALtm')HFw\"[9k[ddzYOiB&3/%3RV,+++++[7'y?l+3?k:\\8*>1)ou:yY)e$3UAz.u $)\\G3j3%yqSjpeGG?4$=X\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "seems_good_Pollard(n1);" }}{PARA 6 "" 1 "" {TEXT -1 364 "145183092028 2858696340707840863082849837403792242083588467815746880619913491564200 80065207861248000000000000000001 is a factor of 145183092028285869 6340707840863082849837403792242083588467815746880619913491564200800652 0786124800000000000143390840408523623646795757486414481762729866673332 2011935980631693582336216210375096928262804009008496640000000009876545 43" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 48 "That took 41 seconds to do on my 166MHz Pentium," }}{PARA 0 "" 0 "" {TEXT -1 47 "and although that is REMARKABLY fast, i t simply" }}{PARA 0 "" 0 "" {TEXT -1 47 "pales into insignificance whe n compared to how " }}{PARA 0 "" 0 "" {TEXT -1 54 "quickly it can be d one by making only a slight change " }}{PARA 0 "" 0 "" {TEXT -1 36 "to the above procedure, namely this:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 48 "The best Pollard (p-1) procedure I can th ink of:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "Pollard_p_minus_1 := pro c(n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "local a, k;" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 10 "a[1] := 2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "for k from 2 while igcd(n, a[k-1] - 1 mod n) = 1 " }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 30 "do a[k] := a[k-1]&^k mod n od;" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 192 "lprint(`After`, k-1, `steps we find that`, \+ \+ igcd(n, a[k-1] - 1 mod n), `is a factor o f `, n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "Pollard_p_minus_1(n1); # the above 'n1' redone" }}{PARA 6 "" 1 " " {TEXT -1 399 "After 77 steps we find that 14518309202828586963 4070784086308284983740379224208358846781574688061991349156420080065207 861248000000000000000001 is a factor of 1451830920282858696340707 8408630828498374037922420835884678157468806199134915642008006520786124 8000000000001433908404085236236467957574864144817627298666733322011935 98063169358233621621037509692826280400900849664000000000987654543" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "TWO SECONDS computation time!!!" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "COMMENT on th is procedure: It has that FIXED '2' " }}{PARA 0 "" 0 "" {TEXT -1 63 " in it - in the line \"a[1] := 2:\" - and so it might be better - " }} {PARA 0 "" 0 "" {TEXT -1 59 "if circumstances ever dictated it (becaus e of a failure to " }}{PARA 0 "" 0 "" {TEXT -1 52 "find a proper facto r) - to make a variation of this " }}{PARA 0 "" 0 "" {TEXT -1 58 "proc edure, by allowing a second global variable ('seed'), " }}{PARA 0 "" 0 "" {TEXT -1 60 "and simply alter the line \"a[1] := 2:\" to \"a[1] : = seed:\". " }}{PARA 0 "" 0 "" {TEXT -1 55 "We will see later that th is is something we need to do." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 45 "For the moment, let us look at a succesio n of" }}{PARA 0 "" 0 "" {TEXT -1 9 "examples." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "#1. The one we have just seen:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "Pollard_p_minus_1(155629) ;" }}{PARA 2 "" 1 "" {TEXT -1 64 "After 6 steps we find that 19 \+ is a factor of 155629\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 3 " #2." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "Pollard_p_minus_1(1556291); \+ # an extra '1' after the end '9'" }}{PARA 2 "" 1 "" {TEXT -1 65 "Afte r 5 steps we find that 11 is a factor of 1556291\n\n" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "#3." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Pollard_p_minus_1(15562911); # an other '1' at the end" }} {PARA 2 "" 1 "" {TEXT -1 65 "After 2 steps we find that 3 is a factor of 15562911\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "COMMENT: 15562911 just ha ppened to have '3' as " }}{PARA 0 "" 0 "" {TEXT -1 56 "a factor, and i t got uncovered quickly. That's because, " }}{PARA 0 "" 0 "" {TEXT -1 42 "with k = 2, we have 2^k - 1 = 2^2 - 1 = 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "#4." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "Pollard_p_minus_1(115562911); # an another extra '1' at the start" }}{PARA 2 "" 1 "" {TEXT -1 69 "After 83 steps we fi nd that 499 is a factor of 115562911\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "#5." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "Pollard_p_m inus_1(2*3*5*7 + 1); # the 4th 'Euclidean number'" }}{PARA 2 "" 1 "" {TEXT -1 62 "After 7 steps we find that 211 is a factor of \+ 211\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "What's happened there? It is simply that (2*3*5*7 + 1) " }}{PARA 0 "" 0 "" {TEXT -1 54 "happens to be a prime \+ (211), and all we have found is " }}{PARA 0 "" 0 "" {TEXT -1 28 "that \+ 211 is a factor of 211." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "The MORAL is that we should FIRST have used a " }} {PARA 0 "" 0 "" {TEXT -1 49 "Fermat test (and NOT just on 2*3*5*7 + 1, but on " }}{PARA 0 "" 0 "" {TEXT -1 29 "ALL the earlier ones as well) " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "#6." } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "Pollard_p_minus_1(341);" }}{PARA 2 "" 1 "" {TEXT -1 62 "After 5 steps we find that 341 is a fac tor of 341\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Is 341 like 211, a prime? NO, it \+ isn't!! 341 (which " }}{PARA 0 "" 0 "" {TEXT -1 46 "you should recogn ise) is a pseudoprime to the " }}{PARA 0 "" 0 "" {TEXT -1 44 "base 2 ( i.e., it is a COMPOSITE number that " }}{PARA 0 "" 0 "" {TEXT -1 38 "' passes Fermat's test to the base 2), " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "2&^340 mod 341; # so '341' MIGHT be prime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "BUT it ISN'T:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "3&^340 mod 341; # showing that 341 fails to the b ase '3':" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#c" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "and t he REAL resaon that the above has NOT " }}{PARA 0 "" 0 "" {TEXT -1 56 "found a factor of 341 is the use of the '2' throughout " }}{PARA 0 " " 0 "" {TEXT -1 50 "the procedure. This, now, is the relevance of my \+ " }}{PARA 0 "" 0 "" {TEXT -1 14 "comment above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "So, let's make the TWO GL OBAL VARIABLE version " }}{PARA 0 "" 0 "" {TEXT -1 54 "of the above pr ocedure, and choose a simple procedure " }}{PARA 0 "" 0 "" {TEXT -1 57 "name, 'pollard' (also - though it is not needed - I have " }} {PARA 0 "" 0 "" {TEXT -1 52 "just used the brief 'divides' in the 'lpr int' line):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Pollard1 := proc(see d, n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "local a, k;" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 13 "a[1] := seed:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "for k from 2 while igcd(n, a[k-1] - 1 mod n) = 1 " }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 30 "do a[k] := a[k-1]&^k mod n od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "lprint(`After`, k-1, `steps we find that`, " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 " igcd(n, a[k-1] - 1 mod n),`i s a factor of `, n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }} {PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "Pollard(2, 341); # as we have already seen" }}{PARA 2 "" 1 "" {TEXT -1 62 "After 5 \+ steps we find that 341 is a factor of 341\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "Pollard(3, 341); # still NO factor , even with 'seed' et to '3'" }}{PARA 2 "" 1 "" {TEXT -1 62 "After 5 steps we find that 341 is a factor of 341\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "Pollard(4, 341); # as expected (si nce '4' is 2^2), NO use" }}{PARA 2 "" 1 "" {TEXT -1 62 "After 5 st eps we find that 341 is a factor of 341\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "Pollard(5, 341); # 'happiness is just arou nd the corner' (D.H.Lehmer)" }}{PARA 2 "" 1 "" {TEXT -1 61 "After 3 \+ steps we find that 31 is a factor of 341\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "Comment: It's interesting to see that the factor '31' " }} {PARA 0 "" 0 "" {TEXT -1 49 "(and 31 - 1 = 2*3*5) was found BEFORE the factor " }}{PARA 0 "" 0 "" {TEXT -1 24 "'11' (and 11 - 1 = 2*5)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "Clearly t he 'Pollard' procedure is SUPERIOR to the" }}{PARA 0 "" 0 "" {TEXT -1 56 "'Pollard_p_minus_1', since it allows room for manoeuvre," }}{PARA 0 "" 0 "" {TEXT -1 57 "and I could have gone for it right at the begin ning, but " }}{PARA 0 "" 0 "" {TEXT -1 54 "I choose not to do so until you could SEE the benefit " }}{PARA 0 "" 0 "" {TEXT -1 12 "of doing s o." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "Eve n though it is superior, I will continue with the " }}{PARA 0 "" 0 "" {TEXT -1 26 "use of the fixed seed '2':" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "#7." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "Pollard_p_minus_1(2*3*5*7*11*13 + 1);" }}{PARA 2 "" 1 "" {TEXT -1 64 "After 29 steps we find that 59 is a factor of 30031 \n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "#8.." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "Pollard_p_minus_1(2*3*5*7*11*13*17 + 1);" }}{PARA 2 " " 1 "" {TEXT -1 66 "After 6 steps we find that 1843 is a facto r of 510511\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "#9. Asking \+ ourselves about that '1843':" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Pol lard_p_minus_1(1843);" }}{PARA 2 "" 1 "" {TEXT -1 64 "After 6 step s we find that 1843 is a factor of 1843\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "Does that mean that 1843 is a prime? Not at all! ! " }}{PARA 0 "" 0 "" {TEXT -1 47 "It COULD have been, but it isn't. \+ We can do a " }}{PARA 0 "" 0 "" {TEXT -1 49 "Fermat test (which shows that 1843 is not prime):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "2&^184 2 mod 1843;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$H(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "T he REAL SECRET as to WHY the Pollard " }}{PARA 0 "" 0 "" {TEXT -1 40 " approach DIDN'T FIND a PROPER factor of " }}{PARA 0 "" 0 "" {TEXT -1 45 "1843 for us is this: 1843 HAPPENS to be the " }}{PARA 0 "" 0 "" {TEXT -1 47 "product of the primes p (=19) and q (=97), and " }}{PARA 0 "" 0 "" {TEXT -1 49 "forming p - 1 and q - 1 gives the numbers 18 an d " }}{PARA 0 "" 0 "" {TEXT -1 49 "96. NOW those two numbers not only have 'small' " }}{PARA 0 "" 0 "" {TEXT -1 44 "prime divisors, but HAP PEN to have the SAME " }}{PARA 0 "" 0 "" {TEXT -1 37 "small prime divi sors, namely 2 and 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "A quotation from Pollard's own ORIGINAL 1974 " }} {PARA 0 "" 0 "" {TEXT -1 57 "PAPER: \"Also [as an example of his metho d in action] ... " }}{PARA 0 "" 0 "" {TEXT -1 59 "p = 27! + 1 [a prime ] has 29 digits, and if q is any other " }}{PARA 0 "" 0 "" {TEXT -1 55 "prime of similar magnitude then pq is easily factored.\"" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "[which in those days - 1974 - was a significant achievement." }}{PARA 0 "" 0 "" {TEXT -1 53 "We will shortly use MUCH LARGER primes than 27! + 1.]" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "NOTE. Th e POINT about the prime p (= 27! + 1) is that " }}{PARA 0 "" 0 "" {TEXT -1 63 "the value of (p - 1) is 27! ( = 27*26*25* ... *5*4*3*2), \+ which " }}{PARA 0 "" 0 "" {TEXT -1 52 "has ONLY 'small' primes dividin g it (the LARGEST of " }}{PARA 0 "" 0 "" {TEXT -1 54 "them being only \+ 23). An example using that prime was " }}{PARA 0 "" 0 "" {TEXT -1 58 "shown earlier, with computation times of 41 and 2 seconds." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "#10. I will ca ll 'p' (= 27! + 1) by the name p27:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "p27 := 27! + 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$p27G\">,++o2 ;_$=/Xp)))3\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "length(p27 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#H" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 47 "q2 := nextprime(23431111289009876546548768549);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q2G\">z&o([law)4!*G66VB" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(q2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#H" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n2 : = p27*q2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n2G\"Zz&o2Ab96Cr!fslHs [\"RH^@AD/>JQ^D" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard_p_minus_1(n2);" }} {PARA 2 "" 1 "" {TEXT -1 144 "After 27 steps we find that 108888 69450418352160768000001 \nis a factor of 255138311904252221512939 148722965725907124111455220768579\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "That factoriz ation of n2 was performed in about " }}{PARA 0 "" 0 "" {TEXT -1 30 "1 \+ second on my 166MHz Pentium." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "One might wish to compare the speed of that " } }{PARA 0 "" 0 "" {TEXT -1 38 "factorization with some other methods." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 43 "Maple h as 4 built-in factorization methods:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 61 "1. The 'Morrison-Brillhart method' (fi rst published in 1975 " }}{PARA 0 "" 0 "" {TEXT -1 64 " in a leadi ng journal of the American Mathematical Society, " }}{PARA 0 "" 0 "" {TEXT -1 56 " the 'Mathematics of Computation'). This is Maple's \+ " }}{PARA 0 "" 0 "" {TEXT -1 65 " 'default' method (i.e. the one i t automatically uses unless " }}{PARA 0 "" 0 "" {TEXT -1 58 " aske d to do otherwise). The command is the familiar " }}{PARA 0 "" 0 "" {TEXT -1 18 " 'ifactor(n)'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 58 "2. The Pollard 'Monte Carlo method' of 1 975; the command " }}{PARA 0 "" 0 "" {TEXT -1 31 " is 'ifactor(n, pollard)'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "3. The (Hendrik, as opposed to Arjen (his brother)) Lenstra \+ " }}{PARA 0 "" 0 "" {TEXT -1 69 " 'elliptic curve method' (first \+ published in the famous 'Annals " }}{PARA 0 "" 0 "" {TEXT -1 68 " \+ of Mathematics', in 1987). This is - in fact - a development " }} {PARA 0 "" 0 "" {TEXT -1 68 " of Pollard's 'p - 1' factoring meth od, and is generally - but " }}{PARA 0 "" 0 "" {TEXT -1 73 " NOT \+ always - superior to it. The command is 'ifactor(n, lenstra)'." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 "4. A li mited method which concentrates on the possibility of " }}{PARA 0 "" 0 "" {TEXT -1 61 " the number having SMALL prime factors. The co mmand is " }}{PARA 0 "" 0 "" {TEXT -1 26 " 'ifactor(n, small)'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "For the first two [for which the clock stayed on ... ] I have placed " }} {PARA 0 "" 0 "" {TEXT -1 64 "the '#' sign before them for safety reaso ns, to prevent possible" }}{PARA 0 "" 0 "" {TEXT -1 33 "re-execution a t some later stage." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "# ifactor(n2 , lenstra);" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "# ifactor(n2, pollard);" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "ifactor(n 2, easy);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%_c57G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "T hat last one, with fast output '_c57', MEANS that the " }}{PARA 0 "" 0 "" {TEXT -1 60 "tested number 'n2' is composite (without finding a f actor), " }}{PARA 0 "" 0 "" {TEXT -1 57 "something that can be shown b y subjecting n1 to a Fermat " }}{PARA 0 "" 0 "" {TEXT -1 19 "test to t he base 2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "2&^(n2 - 1) mod n2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"Z8`)y(*e`-qcF:c;Wh61VIYu]%=iSCZ#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Let's attempt some more Pollard (p - 1) factorizations; " }}{PARA 0 "" 0 "" {TEXT -1 53 "we w ill keep 'p' FIXED at (27! + 1), and choose some " }}{PARA 0 "" 0 "" {TEXT -1 32 "other prime values q2, q3, ... ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "#11." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "q3 := nextprime(59337772890987665465487888877);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q3G\">**)))y[lam()4*GxP$f" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(q3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#H" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n3 := p27*q3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n3G\"Z**))))>*zf. >KH*zvxzYm2=j&y`)[i77Y'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard_p_minus_1(n3); " }}{PARA 2 "" 1 "" {TEXT -1 144 "After 27 steps we find that 10 888869450418352160768000001 \nis a factor of 64612126248853785631 8076646797775799293219035979919888899\n\n" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "Instantly. \+ See how the other methods compare ... ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "#12. Here I will make the prime q 4 have more " }}{PARA 0 "" 0 "" {TEXT -1 36 " than 29 digits t o see ... ." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 50 "q4 := nextprime(9988776112890098765465487685 4965);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q4G\"Ar\\&o([law)4!*G6w() )**" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(q4);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"#K" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n4 := p27*q4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n 4G\"hnr\\&[gKmmdqVqRsZz81A:]stvri!zkw3\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard _p_minus_1(n4);" }}{PARA 2 "" 1 "" {TEXT -1 148 "After 27 steps we find that 10888869450418352160768000001 \nis a factor of 10876 64790627175737250152206137947723970437057666632604854971\n\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "Instantly." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "#13" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "q5 := nextp rime(998877665544998877611289009876546548768549);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q5G\"Kn&o([law)4!*G6w())*\\alw())**" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(q5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#U" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n5 : = p27*q5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n5G\"bon&oZ+Eb)Q5-DzXx c0w=r\"\\0y*\\H%3&Q\"eq\\[m(3\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard_p_minus_ 1(n5);" }}{PARA 2 "" 1 "" {TEXT -1 159 "After 27 steps we find tha t 10888869450418352160768000001 \nis a factor of \n108766484970 58138508429499780549171187605567745792502103885526004768567\n\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "Instantly." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "#14 Here I will make the prime q6 have a LOT " }} {PARA 0 "" 0 "" {TEXT -1 49 " LESS digits than p27 to see what \+ happens." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "q6 := nextprime(768549) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q6G\"'j&o(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(q6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n6 := p27*q6 ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n6G\"Cj&oZQOjt\"**z=Ur@yo$)" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard_p_minus_1(n6);" }}{PARA 2 "" 1 "" {TEXT -1 121 "After 27 steps we find that 1088886945041835216076800000 1 \nis a factor of 8368782171421879991736336384768563\n\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "It found the LARGER factor FIRST. I wonder WHY ... :" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "ifactor(q6 - 1);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#*(-%!G6#\"\"#\"\"\"-F%6#\"$^#F(-F%6#\"%J:F(" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "#15 Here I will make the prime q7 be 65537 [the 4th. 'Fe rmat prime', " }}{PARA 0 "" 0 "" {TEXT -1 66 " the earlier ones being (3) (the 0-th one), 5, 17 and 257]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "q7 := 2^(2^4) + 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%#q7G\"&Pb'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n7 := p27* q7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n7G\"BPb1;CDgban? " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 22 "Pollard_p_minus_1(n7);" }}{PARA 2 "" 1 "" {TEXT -1 95 "After 8 steps we find that 65537 is a factor of \n71362 3837172067545560252416065537\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "It found the \+ smaller factor first. Do you know WHY?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 40 "One can have such fun with this meth od!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "L et's jump back to the beginning of this worksheet, to " }}{PARA 0 "" 0 "" {TEXT -1 53 "the (example of a) 'Euclidean prime' 2*3*5*...*31 +1 ," }}{PARA 0 "" 0 "" {TEXT -1 49 "and to the made-up prime 2^21*3^20*5 ^20*7^20 + 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "#16." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "q8 := product(i thprime(m), m=1..11) + 1; # '11', as 31 is the 11th prime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q8G\"-J,\\g0?" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 40 "n8 := nextprime(1234567890987654321)*q8;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n8G\"?>Gu-:'R&*ykJTbgZ#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard_p_minus_1(n8);" }}{PARA 2 "" 1 "" {TEXT -1 100 "After \+ 31 steps we find that 200560490131 is a factor of \n247605541 316478953961502742819\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "#17." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "q9 := 2^21*3^20*5^20*7^2 0 + 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#q9G\"P,+++++++++-GRus4.R* )eoVc&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "n9 := p27*q9;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#n9G\"fo,++o2;_$=/l\\\"G>$*3*y0!zc3g (Grt?%*yol*QJo*eg" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Pollard_p_minus_1(n9);" }} {PARA 2 "" 1 "" {TEXT -1 163 "After 27 steps we find that 108888 69450418352160768000001 \nis a factor of \n6058968313896568789420 73712876008567900578908931928149650418352160768000001\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Instantly!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "When Pollard mentioned the prime (27! + 1) in his 1974 " }}{PARA 0 "" 0 "" {TEXT -1 55 "paper he probably intended to give an e xample close to " }}{PARA 0 "" 0 "" {TEXT -1 56 "the then limits of co mputational power. I am now going " }}{PARA 0 "" 0 "" {TEXT -1 56 "to take a huge leap forward in size to another prime of " }}{PARA 0 "" 0 "" {TEXT -1 49 "the same form, namely one of the form (m! + 1). " } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "As of Fe b. 1998 it is known that m! + 1 is prime for the " }}{PARA 0 "" 0 "" {TEXT -1 23 "following values of m: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 1 54, 320, " }}{PARA 0 "" 0 "" {TEXT -1 28 "340, 399, 427, 872 and 1477, " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "and i t is an UNSOLVED question as to HOW MANY " }}{PARA 0 "" 0 "" {TEXT -1 22 "such primes there are." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "Also, as of Feb. 1998 it is known that the follow ing" }}{PARA 0 "" 0 "" {TEXT -1 34 "primes produce 'Euclidean' primes: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "2, 3, 5, 7, 11, 31, 379, 1019, 1021, 2657, 3229, 4547," }}{PARA 0 "" 0 "" {TEXT -1 36 "4787, 11549, 13649, 18523 and 23801." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "[IF the College joined th e modern world - and had" }}{PARA 0 "" 0 "" {TEXT -1 46 "World Wide We b (WWW) access for students (and " }}{PARA 0 "" 0 "" {TEXT -1 54 "staf f !!) - you would have been able to find out such " }}{PARA 0 "" 0 "" {TEXT -1 53 "details for yourself. I have just done so from home." }} {PARA 0 "" 0 "" {TEXT -1 54 "One no longer relies on books for such de tails - they " }}{PARA 0 "" 0 "" {TEXT -1 45 "are almost certainly OUT OF DATE even before " }}{PARA 0 "" 0 "" {TEXT -1 49 "they are printed - one now keeps up to date with " }}{PARA 0 "" 0 "" {TEXT -1 49 "the \+ LATEST state of information by accessing the " }}{PARA 0 "" 0 "" {TEXT -1 50 "WWW. Most infant school children in many schools " }} {PARA 0 "" 0 "" {TEXT -1 42 "- even in rural Ireland - know that ... . ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 43 "Once again, it is an UNSOLVED problem as to" }}{PARA 0 "" 0 "" {TEXT -1 38 "HOW MANY 'Euclidean' primes there are." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "#18" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "p116 := 116! + 1;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6# >%%p116G\"jv,++++++++++++?265&e]qvz\"p/'*>hiBGR26,y2;%>*\\eo))pp6=27(f `aiLIj<9`EB\")3iO'>q2U*pbNmRK?t&)e$4c#)>,#)*=X%o3JR$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "length(p116);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$\">" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 148 "q116 := nextprime(10^195 \+ + 69876543212345678987876543887765443456780990909876543675432657897654 321234567876549876543546780098765000111111111199987);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%q116G\"_wF1?6666,+l()4!yYNaw)\\l(ycM7Kaw*ylKanV l()44*4ycMWlx)Qawy)*ycM7Kaw)p++++++++++++++++++++++++++++++++++++++\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "length(q116);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$'>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "n116 := p116*q11 6;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%n116G\"]clF1?6666,+l()4!y!p&) omTrV'eBXNfYNS+J_\\_dt]Ir**RI%4N(GmkBo)R(=>*4[O1_#Qk=c?JFw'pN'y.**GK8+ snE=yO-%Q9!ptkzj\\Ms8f)=[&)42x/Cv,Ky--i*o*e'Q[l3/#*z-#>\\*z60&4vFoGU-% y[D%o`G%e&)o1JB8qyTJlK7)3iO'>q2U*pbNmRK?t&)e$4c#)>,#)*=X%o3JR$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 24 "Pollard_p_minus_1(n116);" }}{PARA 2 "" 1 "" {TEXT -1 650 "After 116 steps we find that 339310868445189820119825609 3588573203239663\\\n55569942077019636620881232653141763303362545359712 0718116969886858499194160778\\\n01110739282362611996046917975705058510 11072000000000000000000000000001 \nis a factor of 339310868445189 820119825609358857320323966355569942077019636\\\n620881232653141787013 233106688558428536842548784024228682775095051179949192027\\\n992040865 483865896896202027832017524047707098548188591372344963796473690143840 \\\n236781826677200133228990378635696762731205618643825206364809919187 398682364662\\\n873509430399971305073575249523100403546593545235864371 416668856907800987650001\\\n11111111200627\n\n" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "WOW!!! That took ONLY (!!!!!!) EIGHT SECONDS " }}{PARA 0 "" 0 "" {TEXT -1 52 "on my 166 MHz Pentium. That is a truly spectacular " }}{PARA 0 " " 0 "" {TEXT -1 14 "factorization." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 45 "CONCLUSION. If nothing else, I hope you \+ are " }}{PARA 0 "" 0 "" {TEXT -1 50 "convinced that Pollard's 'p - 1' \+ factoring method " }}{PARA 0 "" 0 "" {TEXT -1 28 "merits considerable \+ respect." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 1" 384 }{VIEWOPTS 1 1 0 1 1 1803 }