Cryptography Reference
In-Depth Information
time. Similarly, if we want to generate an
r
-bit integer, we just set the first bit to
1 (and also the last bit if we want an odd integer) and generate the remaining bits at
random.
The other ingredient we need to generate random primes is a primality test, so
suppose that we have one called
PrimeTest
that returns “prime” or “composite”
when performed on a positive integer
n
. The algorithm to generate an
r
-bit random
prime is then:
Algorithm 6.3.
Randomprime.
Input
: A length parameter
r
>
0.
Output
: A random
r
-bit prime.
1.
Initialize
a Boolean variable
found := false
;
2.
while not found do
n
←[
2
r
−
2
2
r
−
1
,
−
]
1
;
1;
if PrimeTest
(
n
) = “prime”
then
found := true
end if
end do
;
3.
return
n
.
n
:=
2
n
+
If the algorithm
PrimeTest
used here as a subroutine is a deterministic
polynomial-time algorithm such as AKS or a Las Vegas algorithm such as ECPP,
then
RandomPrime
is a Las Vegas algorithm that correctly generates a random
prime in expected polynomial time. As already mentioned, the AKS test is not fast
enough, in practice, for primes of cryptographic size, but the use of ECPP is viable
for this purpose. However, the probabilistic tests—and, in particular, Miller-Rabin—
are considerably faster and are preferred in many situations, in particular in environ-
ments where computational power is severely limited, as in the case of smart cards.
Moreover, the Miller-Rabin test is usually complemented with some trial division
that will get rid of the numbers with small prime factors and will improve efficiency
even more. The price to pay for using a Monte Carlo algorithm such as Miller-Rabin
is that the output will not necessarily be correct but the prime-generating algorithm
can be made to run in polynomial time in such a way that it outputs a random prime
except with negligible probability.
If the Miller-Rabin algorithm with
k
random bases is used, we know from The-
orem 6.9 that, if
n
is composite, then the algorithm will mistakenly output “prime”
with probability
4
−
k
. Thus one could be tempted to think that
RandomPrime
will return a prime with probability
≤
4
−
k
but this is not correct. The probabil-
ity of error we are interested in here is not the probability that a composite number
passes the test (and is therefore declared prime) but the probability that a number that
passes the test (and is declared prime) turns out to be, nevertheless, composite. This
probability cannot be estimated by using Theorem 6.9 alone as it depends strongly
on the density of primes in the interval where the integers are chosen. To see this,
≥
1
−
