Cryptography Reference
In-Depth Information
r
q
−
1
q
r
−
1
(mod
rq
).
(3) Compute
p
0
≡
−
(4) Find the first prime in the sequence
{
p
0
+2
iqr
}
i
∈
N
, and let
p
=
p
0
+2
iqr
be that prime, which is a strong prime.
Although it is possible to generate primes that are both safe and strong,
the algorithms are not as eGcient as Gordon's algorithm. Furthermore, choos-
ing random primes large enough will generally thwart direct factoring attacks.
The following, also taken from [170], provides a mechanism for generating large
random primes.
Large (Probable) Prime Generation
We let
b
be the input bitlength of the desired prime and let
B
be the input
smoothness bound (empirically determined). Execute the following steps.
(1) Randomly generate an odd
b
-bit integer
n
.
(2) Use trial division to test for divisibility of
n
by all odd primes no bigger
than
B
.If
n
is so divisible, go to step (1). Otherwise go to step (3).
(3) Use the Miller-Selfridge-Rabin (MSR) to test
n
for primality. If it is de-
clared to be a probable prime, then output
n
as such. Otherwise, go to
step (1).
Large (Provable) Prime Generation
Begin with a prime
p
1
, and execute the following steps until you have a
prime of the desired size. Initialize the variable counter
j
=1.
(1) Randomly generate a small odd integer
m
and form
n
=2
mp
j
+1.
(2) If 2
n
−
1
≡
1 (mod
n
), then go to step (1). Otherwise, go to step (3).
(3)
Using the primality test on page 550, with prime bases 2
≤
a
≤
23, if for
any such
a
,
a
(
n
−
1)
/p
≡
1 (mod
n
)
for any prime
p
dividing
n
1, then
n
is prime. If
n
is large enough,
terminate the algorithm with output
n
as the provable prime. Otherwise,
set
n
=
p
j
+1
,
j
=
j
+ 1, and go to step (1). If the test fails go to step (1).
−
1 in the above algorithm,
and a small value of
m
to check, then the test is simple and eGcient.
Note that since we have a known factorization of
n
−
Search WWH ::
Custom Search