{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 }
{CSTYLE "" -1 256 "" 0 14 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 
0 0 2 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Tim
es" 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 "Heading 3" -1 
5 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 1 2 2 2 2 1 1 1 1 }1 1 0 
0 0 0 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 "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" -1 18 1 {CSTYLE "
" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 
0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 
0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 256 35 "Factorization problems a
nd examples" }}{PARA 19 "" 0 "" {TEXT -1 35 "\251Mike May, S.J. 2002, \+
maymk@slu.edu" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }
}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 295 "As we have been looking at RSA,
 it is worthwhile to look at products of primes, p and q, such that n=
p*q is easily factorable by special techniques.  (We want to identify \+
weaknesses in the algorithm to avoid them in implementation.)  Some of
 the exercises from chapter 6 illoustrate the methods." }}}{SECT 0 
{PARA 4 "" 0 "" {TEXT -1 14 "The p-1 method" }}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 433 "The first method to look at is the p-1 method.  This met
hod works when p-1 or q-1 factors as a product of small primes.  (For \+
this worksheet, small primes ar less than 100.)  Without loss of gener
ality assume p-1 factors as a product of small primes.  More specifica
lly assume that p-1 divides 100!.  Then 2^(100!) mod n is congruent to
 1 mod p, and p divides 2^(100!) - 1 mod n. Taking the gcd of that num
ber and n should produce p." }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" 
}{TEXT 257 9 "Example 1" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "Comput
er Exercise 4 asks you to factor 618240007109027021 by the p-1 method.
  We compute 2^(100!) mod n.  " }}{PARA 0 "" 0 "" {TEXT -1 16 "(Be sur
e to use " }}{PARA 0 "" 0 "" {TEXT -1 21 "Power (2,100!) mod n " }}
{PARA 0 "" 0 "" {TEXT -1 27 "rather than\n2^(100!) mod n." }}{PARA 0 "
" 0 "" {TEXT -1 121 "The second tries to compute the power before redu
cing and will run out of memory.  The first reduces mod n at each step
.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "n := 6182400071090270
21;\nb1 := 100!;\nt1 := Power(2, b1) mod n;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"nG\"3@q-4r+S#='" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#
>%#b1G\"it++++++++++++ko\"4@&=^#ePAF3#zp`iG=l:wRYT*3c\"*HK***f<_*Q'Hfo
9i\"Qk#ofr!\\+nEc)Q#*p\"o_T%RW:iK$*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#>%#t1G\"2?!fc$[JP(y" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "Next we f
ind a factor of n.  We test if it is prime and see how p-1 factors." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "factor1 := igcd(t1-1,n);\n
isprime(factor1);\nifactor(factor1-1);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%(factor1G\"*,sQ]#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#*,)-%!G6#\"\"#\"\")\"\"\")-F&6#\"\"$
\"\"&F*)-F&6#F/F(F*-F&6#\"\"(F*-F&6#\"#BF*" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 115 "Finding the other factor is a matter of division.  Once \+
again we check if it is priime and find the factors of q-1." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "factor2 := n/factor1;\nispri
me(factor2);\nifactor(factor2-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%(factor2G\"+@e8pC" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#*()-%!G6#\"\"#F(\"\"\"-F&6#\"\"&F)-F&6
#\"*\"zcM7F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Thus 618240007109
027021 = (250387201)(2469135821);" }}}}{SECT 0 {PARA 5 "" 0 "" {TEXT 
-1 0 "" }{TEXT 258 9 "Example 2" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
118 "Computer Exercise 5 asks you to factor 88348845870908146463724598
90377418962766907.  We repeat the process form above." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "n1:=8834884587090814646372459890377
418962766907:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "b1 := 100!
:\nt1 := Power(2, b1) mod n1;\nfactor1 := igcd(t1-1, n1);" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%#t1G\"KV\"[U[:2FHK-x]0+yl@Qih*" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%(factor1G\"9,+Wlz#o@*)*QWO" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 22 "factor2 := n1/factor1;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%(factor2G\"52pooCCCCCC" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 215 "It is worth noting that this fatcorization gives difficu
lties to the ifactor command which is not looking for such special cas
es.  When we try using the command we give up and interupt the computa
tion after a while." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ifac
tor(n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%!G6#\"52pooCCCCCC\"\"
\"-F%6#\"9,+Wlz#o@*)*QWOF(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
0 "" }}}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 75 "Computer Exercise 6:\n85
975324443166^2 = 462436106261^2 mod 537069139875071." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 61 "factor1 := igcd(85975324443166-4624361062
61,537069139875071);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(factor1G\"(
pk()*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "factor2 := 5370691
39875071/factor1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(factor2G\")f'y
V&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "Exercise 9" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "n := 642401;\nfactor1 := igcd(51610
7*187722-2*7, n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"',Ck" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(factor1G\"%H6" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 21 "factor2 := n/factor1;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%(factor2G\"$p&" }}}{EXCHG }{EXCHG }{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 
1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }