{VERSION 5 0 "IBM INTEL NT" "5.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 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 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 "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 24 "Quadratic Sieve Examples " }}{PARA 19 "" 0 "" {TEXT -1 38 "\251 Mike May, S. J., 2002, maymk@sl u.edu" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 261 "In the context of RSA, factoring the product o f a pair of prime numbers is an important problem. One of the current methods of solving this problem is with a quadratic sieve. It is a d ifficult enough process that we would like to look at an example in de tail." }}{PARA 0 "" 0 "" {TEXT -1 136 "We would like to look at using \+ a quadratic sieve to factor a product of two primes. We start with an n that is a product of two primes." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 24 "Example 1, n = 9091*3271" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "isprime(3271);\nisprime(9091);\nn := 9091*3271;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#%%trueG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%tru eG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\")hmtH" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 328 "We want to look at numbers whose squares that \+ will be a product of small primes mod n. For our example we will cons ider a prime to be small if it is less than 20. We will also cheat a \+ bit on checking if a number is a product of small primes. Instead we \+ will check if it divides the tenth power of the product of small prime s." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "smallprime := 2*3*5*7 *11*13*17*19;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+smallprimeG\"(!p*p *" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 258 "To find numbers whose squar e is a product of small primes we look for numbers whose square is sma ll mod n. We find candidates by taking the square root of n*i and rou nding up. If the result is a factor of (smallprime)^10, we factor it \+ and store the result." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 166 "f or i from 1 to 100 do\n t1 := ceil(sqrt(n*i)):\n t2 := t1^2 mod n: \n t3 := irem(smallprime^10, t2):\n if (t3 = 0) then print(i, t1, \+ t2, ifactors(t2)) fi;\nend do:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#6 \"&'3=\"$D\"7$\"\"\"7#7$\"\"&\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6& \"#J\"&i.$\"&`X\"7$\"\"\"7%7$\"\"$F*7$\"\"(\"\"#7$\"#6F'" }}{PARA 11 " " 1 "" {XPPMATH 20 "6&\"#W\"&sh$\"$+&7$\"\"\"7$7$\"\"#F*7$\"\"&\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#**\"&eU&\"%D67$\"\"\"7$7$\"\"$\" \"#7$\"\"&F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 466 "A line of output lists the i from the square root of n*i, the value m this rounds up t o, the square mod n, and the prime factors with multiplicity of M=m^2 mod n. We look for products of m's where the product of the M's is a \+ perfect square. The rows corresponding to 11 and 14 work. They tell \+ us that (18086*36172)^2 = (2*5^3)^2 mod n. This means n divides (1808 6*36172-2*5^3)(18086*36172+2*5^3). Hopefully one of the factors of n \+ divides each of these factors." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "igcd(18086*36172-2*5^3,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \")hmtH" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "Unfortunately, that is not true so we need to try more numbers to get more relations." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 166 "for i from 1 to 400 do\n \+ t1 := ceil(sqrt(n*i)):\n t2 := t1^2 mod n:\n t3 := irem(smallprime ^10, t2):\n if (t3 = 0) then print(i, t1, t2, ifactors(t2)) fi;\nend do:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#6\"&'3=\"$D\"7$\"\"\"7#7$\" \"&\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#J\"&i.$\"&`X\"7$\"\"\"7 %7$\"\"$F*7$\"\"(\"\"#7$\"#6F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#W \"&sh$\"$+&7$\"\"\"7$7$\"\"#F*7$\"\"&\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#**\"&eU&\"%D67$\"\"\"7$7$\"\"$\"\"#7$\"\"&F*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&\"$C\"\"&C2'\"&7#e7$\"\"\"7&7$\"\"#F*7 $\"\"$F,7$\"\"(F*7$\"#6F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$D\"\"& o4'\"&*R97$\"\"\"7%7$\"\"(F'7$\"#6\"\"#7$\"#7$\"\"\"7&7$\"\"#\"\"$7$F+F'7$\"\"( F*7$\"# " 0 "" {MPLTEXT 1 0 88 "igcd(30362*90922*108653-2^2*3^2*7^3*11*17,n);\nigcd(1 8086*90430-5^4,n);\nigcd(81797-22,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"%rK" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\")hmtH" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"%rK" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Two of \+ these three sets of relations yield a prime factorization of n." }}}} {SECT 0 {PARA 4 "" 0 "" {TEXT -1 23 "Example 2: n= 3701*3571" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "p := 3701;\nq := 3571;\nn := p*q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"%,P" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"%rN" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"n G\")ri@8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "smallprime := 2 *3*5*7*11*13*17*19;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+smallprimeG \"(!p*p*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 150 "for i from 1 t o 400 do\nt1 := ceil(sqrt(n*i)):\nt2 := t1^2 mod n:\nt3 := irem(smallp rime^10, t2):\nif (t3 = 0) then print(i, t1, t2, ifactors(t2)) fi;\nod :" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"\"\"%OO\"%DU7$F#7$7$\"\"&\"\" #7$\"#8F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"(\"%>'*\"&k7\"7$\"\" \"7$7$\"\"#\"#57$\"#6F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#B\"&Nu\" \"%#*\\7$\"\"\"7%7$\"\"#\"\"(7$\"\"$F'7$\"#8F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#E\"&Q&=\"&)RM7$\"\"\"7&7$\"\"#F'7$\"\"$F,7$\"\"(F*7$ \"#8F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#b\"&hp#\"$;'7$\"\"\"7%7$ \"\"#\"\"$7$\"\"(F'7$\"#6F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#()\" &4R$\"%/Z7$\"\"\"7%7$\"\"#\"\"&7$\"\"$F'7$\"\"(F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"##*\"&q[$\"&o*>7$\"\"\"7%7$\"\"#\"\"*7$\"\"$F'7$\"#8F '" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$S\"\"&:I%\"&&G77$\"\"\"7&7$\" \"$F*7$\"\"&F'7$\"\"(F'7$\"#8F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$ f\"\"&Te%\"&#>57$\"\"\"7%7$\"\"#\"\"%7$\"\"(F*7$\"#8F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$2#\"&0B&\"&G\\%7$\"\"\"7%7$\"\"#\"\"(7$\"\"$F-7 $\"#8F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$?#\"&AR&\"%kC7$\"\"\"7%7 $\"\"#\"\"&7$\"\"(F'7$\"#6F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$[$ \"&=y'\"&;)=7$\"\"\"7%7$\"\"#\"\"(7$\"\"$F'7$F+F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$a$\"&+%o\"#m7$\"\"\"7%7$\"\"#F'7$\"\"$F'7$\"#6F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&\"$*Q\"&-<(\"&&QZ7$\"\"\"7%7$\"\"$\"\" '7$\"\"&F'7$\"#8F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"$\"R\"&')=(\"& N]$7$\"\"\"7&7$\"\"&F'7$\"\"(\"\"#7$\"#6F'7$\"#8F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "This gives several possibilities" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "#92,207\nigcd(52305*34870-2^8*3^2*1 3,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\")ri@8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "#87, 348\nigcd(33909*67818-2^6*3*7^2,n);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\")ri@8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "#87, 92, 159\nigcd(33909*34870*45841-2^9*3*7^2*13,n); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"%,P" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "This finally gives the factorization we need." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "1 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }