Cryptography Reference
In-Depth Information
evidence suggests that this is the case and, in fact, that they are sufficiently dense to
allow them—and hence also safe primes—to be found in probabilistic polynomial
time, see [180, 5.5.5]. We will see that safe primes are useful for some public-key
encryption schemes and hence we will briefly discuss how to generate them. In
general, to generate primes of a special form we may use a method similar to the one
just discussed to generate random primes, but the estimation of the running time or
the error probability will be more difficult as it will depend on the density of primes
of the particular form considered. In the specific case of safe primes, it is not obvious
what the density of primes among the numbers of the form 2
q
1, with
q
prime,
is. Let us have a closer look at this in order to estimate the complexity of generating
random safe primes. A first straightforward observation is the following:
+
Lemma 6.1
If p
=
2
q
+
1
is a safe prime, then q
≡
5
(
mod 6
)
and p
≡
11
(
mod 12
)
.
Proof
Since
q
is odd we have that
q
≡
1
(
mod 2
)
and since
q
is prime,
q
≡
(
)
≡
(
)
0
for otherwise
p
would be a multiple of
3, in contradiction with the fact that
p
is also prime. Thus we see that
q
mod 3
. We also have that
q
1
mod 3
≡
(
)
2
mod 3
and this, together with
q
≡
1
(
mod 2
)
implies (using the Chinese remainder theorem)
that
q
≡
5
(
mod 6
)
. This clearly implies that
p
≡
11
(
mod 12
)
.
Thus, in order to generate a random safe prime we can proceed as follows:
1. Choose a random integer
n
of appropriate size and set
q
:=
6
n
+
5 (alternatively,
2).
2. Apply the Miller-Rabin test to
q
.If
q
fails the test go to 1). Otherwise, set
p
choose a random odd integer
n
of appropriate size and set
q
:=
3
n
+
1.
3. Apply the Miller-Rabin test to
p
.If
p
fails the test go to 1). Otherwise, return
p
.
:=
2
q
+
To estimate the running time of this algorithm we only have to estimate the
average number of calls to the Miller-Rabin test. Suppose that we want a safe prime
p
of length
r
. Since the length of
q
is only one bit less and we intend to apply the
algorithm to large primes, we have that len
(
q
)
≈
r
. Then, if we choose
q
in the
congruence class of 5
we have seen that, as a consequence of the PNT
for arithmetic progressions, the expected number of draws until finding a prime is
φ(
(
mod 6
)
6
)
3, so that it is just one-third of the expected number of draws
to find a prime among all the integers of the same size. Once a prime
q
is found we
have to check whether
p
r
ln 2
=
(
r
ln 2
)/
6
=
+
1 is also prime. If the numbers of this form behave
as random numbers in the congruence class of 11modulo 12 (to which all of them
belong), then one would expect that one in each
φ(
12
)
12
2
q
=
(
)/
3 would be
prime and hence the average number of draws of integers
q
would be, approximately,
r
2
ln
2
2
r
ln 2
r
ln 2
r
2
. Since each draw requires either one of two calls to the Miller-
Rabin test with complexity
O
/
9
=
O
(
)
r
3
(
)
, the algorithm would run in expected polynomial
r
5
time
O
. We remark that the argument is not rigorous but one would expect it to
hold if the primes follow the so-called
Cramér's model
, formulated by H. Cramér in
the 1930s, which postulates that if we consider a sequence
(
)
X
n
}
n
=
2
of independent
{
