{VERSION 16 0 "Windows 7" "16.0" }
{USTYLETAB {PSTYLE "Ordered List 1" -1 200 1 {CSTYLE "" -1 -1 "Times"
 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }
{PSTYLE "Ordered List 2" -1 201 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 
1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 36 2 0 2 2 -1 1 }{PSTYLE "Ordered
 List 3" -1 202 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 
0 0 1 }1 1 0 0 3 3 2 72 2 0 2 2 -1 1 }{PSTYLE "Ordered List 4" -1 203 
1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3
 3 2 108 2 0 2 2 -1 1 }{PSTYLE "Ordered List 5" -1 204 1 {CSTYLE "" -1
 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 144 2 0 2 
2 -1 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1
 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 8 8 2 0 2 0 2 2 -1 1 }{PSTYLE "Warning" 
-1 7 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0
 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Annotation Title" -1 205 1 
{CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 
12 2 0 2 0 2 2 -1 1 }{PSTYLE "Fixed Width" -1 17 1 {CSTYLE "" -1 -1 "C
ourier" 1 10 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1
 }{PSTYLE "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2
 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Line Printe
d Output" -1 6 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 2 2
 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Help" -1 10 1 
{CSTYLE "" -1 -1 "Courier" 1 9 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 
0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "C
ourier New" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 
2 -1 1 }{PSTYLE "Diagnostic" -1 9 1 {CSTYLE "" -1 -1 "Courier New" 1 
12 40 120 40 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Maple Output" -1 
11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 
0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Dash Item" -1 16 1 {CSTYLE "" -1 -1 "
Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 
}{PSTYLE "HyperlinkError" -1 206 1 {CSTYLE "" -1 -1 "Courier New" 1 12
 255 0 255 1 2 2 1 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }
{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier New" 1 12 255 0 255 1
 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1
 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0
 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1
 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 
1 }{PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1
 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 4
" -1 20 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 2 2 2 2 2 1 0 0 1 }1
 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 
-1 "Times" 1 14 0 0 0 1 1 1 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 
-1 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 16 0 0 0 1
 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 2 2 0 2 0 2 2 -1 1 }{PSTYLE "Hyperlink
Warning" -1 207 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 1 
2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Left Justified M
aple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2
 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "List Item" -1 14 1 
{CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3
 2 0 2 0 2 2 -1 1 }{CSTYLE "Annotation Text" -1 200 "Times" 1 12 0 0 0
 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Help Maple Name" -1 35 "Times" 1 12 
104 64 92 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "2D Math Bold" -1 5 "Times" 1
 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Help Menus" -1 36 "Times" 1 
12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "2D Math Italic" -1 3 "Times" 
1 12 0 0 0 1 1 2 2 2 2 2 0 0 0 1 }{CSTYLE "Help Normal" -1 30 "Times" 
1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Plot Text" -1 28 "Times" 1 
8 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Help Nonterminal" -1 24 "Couri
er" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Help Heading" -1 26 "Ti
mes" 1 14 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Help Italic" -1 42 "Ti
mes" 1 12 0 0 0 1 1 2 2 2 2 2 0 0 0 1 }{CSTYLE "Help Variable" -1 25 "
Courier" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Help Italic Bold" 
-1 40 "Times" 1 12 0 0 0 1 1 2 2 2 2 2 0 0 0 1 }{CSTYLE "Default" -1 
38 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Help Underlined \+
Italic" -1 43 "Times" 1 12 0 0 0 1 1 2 1 2 2 2 0 0 0 1 }{CSTYLE "Maple
 Input" -1 0 "Courier New" 1 12 120 0 14 1 2 1 2 2 1 2 0 0 0 1 }
{CSTYLE "2D Output" -1 20 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 0 0 0 1 }
{CSTYLE "2D Math Bold Small" -1 10 "Times" 1 1 0 0 0 1 2 1 2 2 2 2 0 0
 0 1 }{CSTYLE "2D Math Small" -1 7 "Times" 1 1 0 0 0 1 2 2 2 2 2 2 0 0
 0 1 }{CSTYLE "Page Number" -1 33 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0
 0 1 }{CSTYLE "Output Labels" -1 29 "Times" 1 8 0 0 0 1 2 2 2 2 2 2 0 
0 0 1 }{CSTYLE "Plot Title" -1 27 "Times" 1 10 0 0 0 1 2 1 2 2 2 2 0 0
 0 1 }{CSTYLE "Help Emphasized" -1 22 "Times" 1 12 0 0 0 1 1 2 2 2 2 2
 0 0 0 1 }{CSTYLE "2D Math Symbol 2" -1 16 "Times" 1 12 0 0 0 1 2 2 2 
2 2 2 0 0 0 1 }{CSTYLE "Maple Comment" -1 21 "Courier" 1 12 0 0 0 1 2 
1 2 2 2 2 0 0 0 1 }{CSTYLE "Caption Reference" -1 201 "Times" 1 12 0 0
 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 202 "Co
urier New" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "Code" -1 203
 "Courier New" 1 12 255 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "2D Inert O
utput" -1 204 "Times" 1 12 144 144 144 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE 
"2D Math Italic Small" -1 205 "Times" 1 1 0 0 0 1 1 2 2 2 2 2 0 0 0 1 
}{CSTYLE "2D Comment" -1 18 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }
{CSTYLE "Help Underlined Bold" -1 41 "Times" 1 12 0 0 0 1 1 1 2 2 2 2 
0 0 0 1 }{CSTYLE "Copyright" -1 34 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 
0 0 1 }{CSTYLE "Hyperlink" -1 17 "Times" 1 12 0 128 128 1 2 2 1 2 2 2 
0 0 0 1 }{CSTYLE "Help Underlined" -1 44 "Times" 1 12 0 0 0 1 2 2 1 2 
2 2 0 0 0 1 }{CSTYLE "Prompt" -1 1 "Courier" 1 12 0 0 0 1 2 1 2 2 2 2 
0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0
 1 }{CSTYLE "2D Input" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 
}{CSTYLE "Header and Footer" -1 206 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0
 0 0 1 }{CSTYLE "Text" -1 207 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1
 }{CSTYLE "Help Notes" -1 37 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 
}{CSTYLE "Help Bold" -1 39 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }
{CSTYLE "Equation Label" -1 208 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0
 1 }{CSTYLE "LaTeX" -1 32 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }
{CSTYLE "Atomic Variable" -1 209 "Times" 1 12 175 0 175 1 1 2 2 2 2 2 
0 0 0 1 }{CSTYLE "Popup" -1 31 "Times" 1 12 0 128 128 1 1 2 1 2 2 2 0 
0 0 1 }{CSTYLE "Dictionary Hyperlink" -1 45 "Times" 1 12 147 0 15 1 2 
2 1 2 2 2 0 0 0 1 }{CSTYLE "Caption Text" -1 210 "Times" 1 12 0 0 0 1 
2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Help Fixed" -1 23 "Courier" 1 10 0 0 0 1
 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "" -1 211 "Times" 1 20 0 0 0 1 2 2 2 2 2
 2 0 0 0 1 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 211 22 "(p-1)-factoring method" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 145 "This method is designed to fa
ctor composite numbers n such that for at least one of the prime facto
rs p of n, (p-1) is a product of small primes." }}}{EXCHG {PARA 0 "" 0
 "" {TEXT 207 178 "To illustrate the attck, let's first construct a pr
ime p, such that p-1 is a product of only small primes. We start from \+
some even big number p0 that is a product of small primes" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "p0:=2^5*13^50;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "\"enof\\B7:W\"Q[7'yvq84Q&[l\\m?LN^tLf\"" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT 207 36 "p0+1 need not be a prime, of course:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "isprime(p0+1);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT 207 181 "We are looking for a prime number of the form k*p0+1 fo
r small values of k. The distribution of prime numbers suggests that s
uch k is usually not hard to find simply by brute force:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "for k from 1 to 200 do\n" }{MPLTEXT
 1 0 27 "  if isprime(k*p0+1) then \n" }{MPLTEXT 1 0 16 "    P:=k*p0+1
; \n" }{MPLTEXT 1 0 12 "    break; \n" }{MPLTEXT 1 0 10 "  end if;\n" 
}{MPLTEXT 1 0 7 "end do;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 31 "So o
ur desired prime number is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
2 "P;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"fn\\cXeMm&e>KPZO$y]+>R.i9t_')
['3r_<" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "isprime(P);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*protectedG" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT 207 39 "And the prime decomposition of (p-1) is" }{TEXT 
207 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "ifactor(P-1);" }
}{PARA 11 "" 1 "" {XPPMATH 20 "*()-I!G6\"6#\"\"#\"\"&\"\"\"-F%6#\"#6F*
)-F%6#\"#8\"#]F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 56 "Now we choos
e another large prime number Q and form n=PQ" }}}{EXCHG {PARA 0 "> " 0
 "" {MPLTEXT 1 0 37 "Q:=nextprime(rand(10^100..10^120)());" }}{PARA 11
 "" 1 "" {XPPMATH 20 "\"cr8\"op@&3h(yJy)*>j>_ACT5bMu$QeH__OV\"zTz!zav3
-4,OZ$y0cHc;%[9\"ph%oO:F?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 
"n:=P*Q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"]vP.sd5M`?G(y8E:P\\M\"3MIW
!)z:okhcT9<?*eqoIM)=E\\fS'[*p62p.2>v:4vZR_vspO518w#4AT\"Q5$)Rw4o+aL(Q2
&fU,`N" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 24 "Note that maple comman
d " }{TEXT 207 84 "ifactor(n); fails to factorize this n. We will now \+
factorize n using (p-1) algorithm" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
207 17 "Choose a base 'a'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 
"a:=2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT 207 13 "and a bound B" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 9 "B:=13*50;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$]'" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT 207 20 "Now compute b=a^(B!)" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 5 "b:=a;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i from 1 to B do\n"
 }{MPLTEXT 1 0 17 "  b:=b&^i mod n;\n" }{MPLTEXT 1 0 7 "end do:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "b;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "\"]v>rk([5<GD$[KuL1ayJ[$GgXX,Vq@vPIw^e@#GJ7?bz>a=Xj@&==6`
#Q<2X5yl*>X#G%Rw$[`n;<))QtSwi?u*egLq27JLd<#" }}}{EXCHG {PARA 0 "" 0 ""
 {TEXT 207 101 "According to (p-1) method, if p-1 divides b, then p di
vides (b-1) and also n, so p divides their gcd:" }}}{EXCHG {PARA 0 "> 
" 0 "" {MPLTEXT 1 0 11 "gcd(b-1,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "
\"fn\\cXeMm&e>KPZO$y]+>R.i9t_')['3r_<" }}}{EXCHG {PARA 0 "" 0 "" {TEXT
 207 40 "This is our factor that we started from." }}}{EXCHG {PARA 0 "
" 0 "" {TEXT 207 122 "************************************************
**********************************************************************
****" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 216 "The above attack shows \+
that in RSA, we have to choose primes p and q such that both p-1 and q
-1 have large prime factors. We can achieve it similarly to the above \+
method. First, we start from a large prime factor p0:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "p0:=nextprime(rand(10^50..10^60)())
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"gn>g[+=kji?Ijo\"HGKec/l]up9Y<()>!
y&)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 121 "Then we are looking for \+
a prime of the form (s+i)*p0+1, where s is a large number and i runs f
rom 1 to some small number." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
24 "s:=rand(10^70..10^80)();" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"[py7([
uGqD_>9pKM#4<j,)z&e4S]^n[1'Hb^U\"e3Z$y&)>(" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 23 "for i from 1 to 200 do\n" }{MPLTEXT 1 0 31 "  if is
prime((s+i)*p0+1) then \n" }{MPLTEXT 1 0 20 "    P:=(s+i)*p0+1; \n" }
{MPLTEXT 1 0 12 "    break; \n" }{MPLTEXT 1 0 10 "  end if;\n" }
{MPLTEXT 1 0 7 "end do;" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT 207 32 "So our \"secure\" prime number is:" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 2 "P;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"gs,m&Hlt
!=b/_*G;zCDrT:u5]bo=o9u$\\'4=\\fH=Xc.!o>8b:RJufx:A,&z\"Rc(QSik/ZOi4\"[
&\\<'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 51 "A quick check that P-1 \+
has a large prime factor p0:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 11 "P-1 mod p0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT 207 25 "Similarly we construct Q:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "q0:=nextprime(rand(10^50..10^60)())
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"gn`/Z))p'=I!po-11mV4%p.,#HOS[%piP
My&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 121 "Then we are looking for \+
a prime of the form (s+i)*p0+1, where s is a large number and i runs f
rom 1 to some small number." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
24 "s:=rand(10^60..10^68)();" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"_oFLqo
xrn/:FNiMU`M**pru]F<NFJj0JK>$3S%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT
 1 0 23 "for i from 1 to 200 do\n" }{MPLTEXT 1 0 31 "  if isprime((s+i
)*q0+1) then \n" }{MPLTEXT 1 0 20 "    Q:=(s+i)*q0+1; \n" }{MPLTEXT 1 
0 12 "    break; \n" }{MPLTEXT 1 0 10 "  end if;\n" }{MPLTEXT 1 0 7 "e
nd do;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 32 "So our \"secure\" prim
e number is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "Q;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "\"[sJZM0*o%p#oW#=\\#>ltL?#=i$f^A@z1#R#pF)4*Rt7
zWdel8GO+s\")=r6:p\\--i!G&=()p$>XD" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
207 51 "A quick check that P-1 has a large prime factor p0:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Q-1 mod q0;" }}{PARA 11 "" 1
 "" {XPPMATH 20 "\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 36 "Now  o
ur open key will include n=PQ:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 7 "n:=P*Q;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",$I\"PG6\"\"[sJZM0*o%p
#oW#=\\#>ltL?#=i$f^A@z1#R#pF)4*Rt7zWdel8GO+s\")=r6:p\\--i!G&=()p$>XD" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 66 "Out of curiosity, let's try to
 factorize this n with (p-1) method:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 5 "b:=2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "B:=1500;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "\"%+:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i
 from 1 to B do\n" }{MPLTEXT 1 0 17 "  b:=b&^i mod n;\n" }{MPLTEXT 1 
0 7 "end do:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 207 88 "Now when we comp
ute gcd(b-1,n), we get a useless trivial factor, so our attack failed \+
:(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "gcd(b-1,n);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}{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 }