{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 }{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 "Tex t 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 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "# ferm_fac.ms\n" } {TEXT -1 723 "## Is 2^p-1 prime for infinitely many p? ##\n# I s 2^(2^n)+1 prime for some n > 4? #\n# \+ #\n# John B. Cosgrave, #\n # Department of Mathematics, #\n# St. Patric k's College, #\n# Drumcondra, \+ #\n# Dublin 9, #\n# IRE LAND. #\n# \+ #\n# Home e-mail: johnbcos@iol.ie #\n# Coll ege 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\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 124 "This elementary worksheet deals with 'Fe rmat factorisation', which is an elementary method for factoring a com posite number." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 351 "This is NOT a very PRACTICAL method, but at the same tim e it should NOT be ignored, and - for example - if someone were foolis h enough in using the RSA cryptographic method to choose their two pri mes 'p' and 'q' to be TOO NEAR to each other, then their public modulu s 'n' (n = p*q) can be easily factored using the Fermat method, as we \+ will see below." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 83 "Let us remind ourselves of the simple IDEA behind 'Fermat factorisation/factoring':" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 197 "[First we 'read in' (it's like 'with'(numtheory) ) from the 'Maple library' the useful 'issqr' command - the 'issqr' is an abbreviation of 'is_a_square', and is like the familiar 'isprime' \+ command.]" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "readlib(issqr):" }} {PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "issqr(81);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "issqr(83);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "n1 := 91;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n1 \+ + 0^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n1 + 1^2); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n1 + 2^2);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n1 + 3^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "That last one tells us that 91 + 3^2 is a square. Which square ?:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "sqrt(n1 + 3^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 83 "and so we have: 91 + 3^2 = 10^2, and so 91 = 10^2 - 3^2 = (10 - 3)*(10 + 3) = 7*13." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "n2 := 121;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n2 + 0^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "That immediat ely tells us that 121 is itself a square, and so it immediately factor s as:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "sqrt(121 + 0^2);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 6 "11*11." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "n3 := 13;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 0^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 1^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 2^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 3^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 4^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 5^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "issqr(n3 + 6^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 30 "but that MERE LY tells us that:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "sqrt(n3 + 6^2) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 96 "and so we have: 13 + 6^2 = 7^2, and so 13 = 7^2 - 6^ 2 = (7 - 6)*(7 + 6) = 1*13, and 13 is prime." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "Now to make the Fermat method i nto a procedure. I give two ways." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 41 "In Procedure #1 the global variables are: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "1. ' n' - that will be the number we are trying to factor." }}{PARA 0 "" 0 "" {TEXT -1 50 "2. 'start' - that will be where we start testing." }} {PARA 0 "" 0 "" {TEXT -1 42 "3. 'finish' - that's where we test up to ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "And \+ the local variables are:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 60 "1. 'k' - it will be the number whose square is ad ded to 'n'" }}{PARA 0 "" 0 "" {TEXT -1 206 "2. 's' - IF we eventually get a 'k' such that (n + k^2) comes out to be a square, then 's' is \+ DEFINED to be the number whose square IS (n + k^2). [IF that does hap pen, then we have n + k^2 = s^2, and so " }}{PARA 0 "" 0 "" {TEXT -1 67 "n = s^2 - k^2 = (s - k)*(s + k), which explains the 'lprint' line. ]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 134 "NOT E. The 'RETURN()' device is Maple's way of being instructed to then di scontinue [IF a 'k' has been found] any further calculations." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "Procedure #1." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "Fermat_factor := proc(n, st art, finish) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "local k, s;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "readlib(issqr):" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 29 "for k from start to finish do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " if issqr(n + k^2) then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " s := sqrt(n + k^2); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 66 " lprint(n, `factors as the product of `, s - k, `a nd`, s + k); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " RETURN()" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " fi " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od " }}{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 26 "Fermat_factor(12 1, 0, 30);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Fermat_factor(91, 0, 30);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 25 "Fermat_factor(83, 0, 30);" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 79 "The fact that there was NO output there j ust tells us that NONE of the numbers:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 47 " 83 + \{0^2, 1^2, 2^2, 3^2, \+ ... , 30^2\}" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 120 "is a square, and if we try a bit more (and the furthest to tes t to - in general for an odd number 2*r + 1, is as far as " }}{PARA 0 "" 0 "" {TEXT -1 14 "r - is to 41):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "Fermat_factor(83, 31, 41);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 124 "And now the other for m of the Fermat procedure. It is almost identical to the above one, ex cept here I make use of 'while'. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 13 "Procedure #2." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "Fermat_fact := proc(n, start, finish) " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "local k, s;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "readlib(issqr):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "for k from start to finish " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " while not is sqr(n + k^2) do k od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " if issqr (n + k^2) then " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " s := sqrt(n \+ + k^2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 64 " lprint(n, `factors a s the product of `, s - k, `and`, s + k)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 " else lprint(n, `does not Fermat factorise in the ch osen range`)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " fi;" }}{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 23 "Fermat_fact(121, 0, 0);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 23 "Fermat_fact(91, 0, 45);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 23 "Fermat_fact(83, 0, 39);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 23 "Fermat_fact(83, 0, 40);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "Let's have \+ a look at an RSA example." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 33 "Suppose someone chose as follows:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "p[1] := nextprime(876549912654721557675432113123 12321245216559009239994365);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "q[1] := nextprime(p[1] + 100);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "n[1] := p[1]*q[1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Fermat_factor(n[1], 0, 1000);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 27 "Fermat_fact(n[1], 0, 1000);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 178 "Now I am going to CHANGE the '100' in \+ the 'q[1] := nextprime(p[1] + 100)' to 3000, and change all those 1's \+ to 2's. However I am going to leave unchanged the 'finish' of '1000': " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "p[2] := nextprime(111118765499126547215576754321131231232124521655900 9239994365);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "q[2] := nex tprime(p[2] + 3000);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "n[2 ] := p[2]*q[2];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Fermat_f actor(n[2], 0, 1000);" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Fermat_fact(n[2], 0, 1000);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 221 "You see what has happened? The trial range of 0 to 1000 wasn't LONG ENOUGH, and so we need to test in a further trial range, \+ and NOT redo calculations already done; that is, we DON'T go for a ran ge like (say) 0 to 2000, " }}{PARA 0 "" 0 "" {TEXT -1 33 "but rather o ne like 1001 to 2000:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "Fermat_fac tor(n[2], 1001, 2000);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "F ermat_fact(n[2], 1001, 2000);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "COMMENTS." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 289 "1. The Fermat method is all very well for factoring \+ a number IF it HAPPENS to be the product of two integers that are CLOS E TO EACH OTHER IN SIZE, but it is USELESS otherwise, and does NOT po se a threat to someone using RSA, providing the user is sensible in t heir choice of two primes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 117 "2. The above remarks might appear to be rather dismissive of the Fermat method, and I ought to record two facts: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 "ONE. \+ The method CAN be SPEEDED up a bit by making certain elementary observ ations:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 " Squares, when expressed in the base 10 have ONLY got certain F INAL digits: 0, 1, 4, 5, 6, 9." }}{PARA 0 "" 0 "" {TEXT -1 81 " To p ut it another way, squares CANNOT end in 2, 3, 7 or 8. That's element ary:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 100 " For n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (mod 10), we have n^2 = 0, 1, 4, 9, 6, 5, 6, 9, 4, 1 (mod 10)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 442 "An immediate consequence: When - by han d - we were trying to 'Fermat factorise' 91 (for example) we began by adding 1^2 to it to see IF we got a square. We got '92', and it wasn 't a square. HOW, though, did we do that? Because it was so small, w e could see it (92) was between 81 (9 squared) and 100 (10 squared), a nd so we would have rejected it. Probably the same with 91 + 2^2, and \+ then we found a lucky factorisation on the next one:" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 " 91 + 3^2 = 1 00 = 10^2, and so " }}{PARA 0 "" 0 "" {TEXT -1 49 " 91 = 10^2 - 3 ^3 = (10 - 3)*(10 + 3) = 7*13." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 255 "IF, however, we had been trying a larger number than 91, let's say - for example - that we had been testing 13 161, which - like 91 - ends in a '1', then we could save ourselves (AN D computing TIME when MUCH LARGER numbers are involved) by noting that for:" }}{PARA 0 "" 0 "" {TEXT -1 8 " " }}{PARA 0 "" 0 "" {TEXT -1 62 " k = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (mod \+ 10), " }}{PARA 0 "" 0 "" {TEXT -1 59 " k^2 = 0, 1, 4, 9, 6, 5, 6, 9, 4, 1 (mod 10)," }}{PARA 0 "" 0 "" {TEXT -1 53 "13161 + k ^2 = 1, 2, 5, 0, 7, 6, 7, 0, 5, 2 (mod 10)," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "and so (13161 + k^2 ) could NO T be a square for k ending (base 10) in a '1', '4', '6' or '9'." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 140 "That rep resents a SAVING of 40% in computation time, and so in ATTEMPTING a Fe rmat factorisation of 13161 one would ONLY test these numbers:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 43 " \+ 13161 + " }}{PARA 0 "" 0 "" {TEXT -1 65 "( \+ 0^2, __ , 2^2, 3^2, __ , 5^2, __ , 7^2, __ , 8^2, __ " }} {PARA 0 "" 0 "" {TEXT -1 60 " 10^2, __ , 12^2, 13^2, __ , 15^2, __ , 1 7^2, __ , 18^2, __ " }}{PARA 0 "" 0 "" {TEXT -1 6 " ..." }}{PARA 0 " " 0 "" {TEXT -1 13 " ... etc. )" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 101 "YOU use that approach to continue - by h and, with a calculator - an attempted factorisation of 13161." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 43 "QUESTION \+ to you: What about other numbers?" }}{PARA 0 "" 0 "" {TEXT -1 54 "Wha t about numbers (like, say, 13163) that end in a 3?" }}{PARA 0 "" 0 " " {TEXT -1 54 "What about numbers (like, say, 13167) that end in a 7? " }}{PARA 0 "" 0 "" {TEXT -1 54 "What about numbers (like, say, 13169) that end in a 9?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "What % saving in computation time is there in those cases ?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "The re are OTHER simple devices that one can further use to reduce computa tion time, BUT they are ONLY" }}{PARA 0 "" 0 "" {TEXT -1 85 "scratchin g at the surface, and they pose no threat to a correctly chosen RSA ex ample." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 104 "TWO. The Fermat method was brilliantly extended in 1982 to what \+ was called the 'quadratic sieve' by the" }}{PARA 0 "" 0 "" {TEXT -1 103 "American mathematician Carl Pomerance [though there were many, ma ny others between Fermat and Pomerance" }}{PARA 0 "" 0 "" {TEXT -1 133 "who contributed ideas]. That (very, very advanced) method had it s greatest triumph by factoring the famous 'RSA_129' number in 1994." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "62 48 0" 97 } {VIEWOPTS 1 1 0 1 1 1803 }