Cryptography Reference
In-Depth Information
Prime Generator—Gordon's Algorithm This algorithm produces strong primes.
When we produce integers that are the product of large strong primes, these integers are
highly resistant to factoring methods.
1.
Generate two large random primes
of approximately the same size. (Use an appro-
priate random number generator and primality test; see Chapter 11 on primality testing.)
s
and
t
2.
Choose an integer
i
*, then find the first prime
r
= 2
it
+ 1, where
i
=
i
*,
i
* + 1,
i
* + 2, . . . .
s r 2 (mod
3.
Compute
z
= the lnr of
r
).
4.
Calculate
p
* = 2
zs
1.
5.
Choose an integer
k
*, then find the first prime
p
=
p
* + 2
krs
, where
k
=
k
*,
k
* + 1,
k
* +
2, . . . .
6. p
is a strong prime.
s r 1
To see that
p
is indeed a strong prime, note that by FLT we have
1 (mod
r
). Thus,
p
* = 2
zs
1
2
s r 2
s
1
2
1
1
1 (mod
r
), and
p * = 2 zs 1 1 (mod s ).
This immediately gives us what we need:
(a)
p
1 =
p
* + 2
krs
1
0 (mod
r
);
r
= 2
it
+ 1 is a large prime factor of
p
1
(b)
p
+ 1 =
p
* + 2
krs
+ 1
0 (mod
s
);
s
is a large prime factor of
p
+ 1
(c)
r
1 = 2
it
0 (mod
t
);
t
is a large prime factor of
r
1.
p
and we establish that
is a strong prime.
E XAMPLE . The following demonstrates finding a strong prime using Gordon's algorithm. First
we generate
s
and
t
, two primes of about the same size.
s
=
649257745123755764564298232583183358105018398492925296182752230219795813
315606717730413881037389513739598704819556327738654940708820981641744821
701213543
t =
459229816351936145409407672206871372046265685062392744762039282823998800
862208949389232433994508929505925943890562601701058936427954733705485851
046387127
Now, we look for the first prime r of the form 2 it + 1, where i begins at 1. In this case,
we get:
r
=
596998761257516989032229973868932783660145390581110568190651067671198441
120871634206002164192861608357703727057731382211376617356341153817131606
36030326511
Search WWH ::




Custom Search