Cryptography Reference
In-Depth Information
4
−
k
, we have that the probability of error of the prime-finding algorithm
will, in this case, be
P
(
,
)<
P
r
k
4
−
r
(
,
)
=
(
)
which is certainly negligible in the length
parameter
r
. We stress that, in practice, there is no need to increase the number of
bases used for the Miller-Rabin test and using a constant value (such as
k
r
r
O
=
20
25) is sufficient for, once the error probability is below, say 10
−
50
, there
is no need to make it even smaller for larger numbers (and, as remarked before,
this probability will anyway decrease as the number size
r
increases). If
k
is kept
constant, then the prime-finding algorithm will run in polynomial time
O
or
k
=
r
4
.
Miller-Rabin is, due to its efficiency, the test of choice to obtain large primes
for cryptographic use. The “probable primes” furnished by the test have been called
industrial-grade primes
because they are very likely prime but have not been
proved
to be prime. In relation with this it might be pointed out that, from an industrial point
of view, the quality of these probable primes is orders of magnitude above anything
produced in the usual industrial manufacturing processes. It should also be pointed
out that
any
large prime which is actually being used in cryptography is in some sense
an industrial-grade prime. Even if a deterministic algorithm has been used to prove
5
that the number is prime, the algorithm must be implemented and run on a machine.
The implementation might have bugs and the machine will most likely suffer from
hardware errors. Both these facts might conceivably affect the result of applying the
algorithm and, even if the probability that they lead to an erroneous result is low,
will it be lower than the error probability of Miller-Rabin? It seems a bit naive to
assume, prima facie, that this will indeed be the case
(
)
...
All the variants of the
RandomPrime
algorithm are probabilistic since they re-
quire as input random integers of a given length, which are subsequently tested for
primality. From a theoretical point of view it is an interesting problem to find a deter-
ministic version of
RandomPrime
but there is no obvious way to “derandomize”
this algorithm. Thus the following problem, as described by Tao (cf. [157]), is open
6
:
Find a deterministic algorithm which, when given an integer
r
, is guaranteed to find a prime
of at least
r
digits in length of time polynomial in
r
. You may assume as many standard
conjectures in number theory (e.g. the Extended Riemann hypothesis) as necessary, but avoid
powerful conjectures in complexity theory (e.g.
P
=
BPP
) if possible.
This problem is discussed in several threads accessible from [157] and also in [192].
6.3.1 Generating Safe Primes
Sometimes in cryptography it is desirable to generate random
r
-bit primes of a
particular form. For example, a
safe prime
is a prime of the form
p
1, where
q
is also prime (so that
q
is a Sophie Germain prime). As we have mentioned, it is not
known whether there are infinitely many Sophie Germain primes but the heuristic
=
2
q
+
5
Let us assume here that the mathematical proof gives absolute certainty, something that is by no
means obvious and is subject to much philosophical debate.
6
This problem highlights again the difference between primality testing and finding random primes.
