{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 "# fast_gcd.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 214 "In the Pollard 'Monte Carlo' (also known as 'rho') and 'p - 1' factoring methods, the Euclidean algorithm for \+ calculating gcd's plays a fundamental role. These two remarkable meth ods have beautiful ideas at their " }}{PARA 0 "" 0 "" {TEXT -1 190 "ro ots, but they would be utterly useless (from a computational point of \+ view) were it not for the SPEED of the Euclidean algorithm, the SPEED \+ at which the gcd calculation can be carried out." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 "The purpose of this works heet is to demonstrate the SPEED of the Euclidean algorithm." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "gcd_and_steps := proc(A, B)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "local a, b, r, k, K;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "a[1] := A: b[1] := B: r[1] := a[1] mod b[1]:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "if r[1] = 0 then lprint( `the great est common divisor of `, A, `and `, B,`is`, b[1])" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 43 " else for k from 2 while r[k - 1] <> 0 do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 " a[k] := b[k - 1]: b[k] := r[ k - 1]: r[k] := a[k] mod b[k]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " \+ od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 75 " lprint( `the greates t common divisor of `, A, `and `, B,`is`, r[k - 2]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 61 " seq([a[K], b[K], iquo(a[K], b[K]), r[K]], K = 1..k - 1); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "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 26 "gcd_and_steps(12321, 121);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "You shou ld see what the output MEANS:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 124 "The first output, '[12321, 121, 101, 100 ]' is simply recording the numbers in the FIRST division in the Euclid ean algorithm:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "12321 = 121*101 + 100 (a[1] = b[1]*q[1] + r[1])," }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "followed \+ by the second, third, ... divisions." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "And rec all the DIFFICULTY of factoring:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "p := nextprime(1234565432134543);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "q := nextprime(56789876512321);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "n := p*q;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "ifactor(n); # the clock STAYS on, and I have stopped \+ it" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "You and I can SEE that the ONLY factors of 'n' are 1, p, q and n." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "Now let's do this:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "P := nextprime(9999565432134543);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "Q := nextprime(8888987651 2321);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "N := P*Q;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "# ifactor(N); I have placed \+ the comment sign before the command" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " # to prevent execution " }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Again, you and I can SEE that the \+ ONLY factors of 'N' are 1, P, Q and N." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 73 "And, what is the gcd of 'n' and 'N'? \+ We can SEE it is '1', because ... ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 72 "Now to see how FAST the Euclidean algor ithm when applied to 'n' and 'N':" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "gcd_and_steps(n, N);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 175 "COMMENT: What should IMPRESS one (with that and other similar ca lculations) is that whereas the factoring of 'n' or 'N' is SLOW, their gcd can be calculated ALMOST INSTANTLY." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "1 3 0" 6 } {VIEWOPTS 1 1 0 1 1 1803 }