Cryptography Reference
In-Depth Information
The full-blown test function
prime_l()
integrates the division sieve and
the Miller-Rabin test. To retain maximum flexibility the function is constituted
in such a way that the number of divisions in the pretest and the number of
passes through the Miller-Rabin test can be passed as parameters. To simplify the
situation in applications, the macro
ISPRIME_L(CLINT n_l)
can be used, which in
turn calls the function
prime_l()
with preset parameters.
There is differing advice in the literature in relation to the open question of
how many repetitions of the Miller-Rabin test should be made in order to ensure
reliable results. For example, [Gord] and [Schn] recommend five repetitions for
cryptographic purposes, while the algorithm in [Cohe] prescribes 25 passes. In
[Knut], the recommendation is that in 25 passes through the test, the number of
errors for a set of a billion candidates accepted as prime numbers is under
10
−
6
,
although the value
25
is not explicitly endorsed, and he asks the philosophical
question, “Do we really need to have a rigorous proof of primality?”
10
For the application area of digital signatures, there is the opinion that error
probabilities less than
2
−
80
10
−
24
in the generation of prime numbers is
acceptable (in Europe, the bound
2
−
60
≈
≈
10
−
18
is also under discussion), so
that errors are almost entirely excluded even when large numbers of keys are
generated. In [RegT] it is suggested that in 2010,the threshold value should be
lowered to
2
−
100
. Applied to the estimate of the probability of error by Rabin, this
would mean that 40, respectively 30, rounds of Miller-Rabin tests would be run,
with longer calculation times as the size of the numbers being tested grows. In
fact, however, there exist very much sharper estimates that depend not only on
the number of passes, but also on the length of the prime number candidate (see
[DaLP] and [Burt]). In [DaLP], the following inequalities are proved, where
p
l,k
denotes the probability that a randomly selected odd number with
l
binary digits
that is declared prime after
k
passes through the Miller-Rabin test is actually
composite:
p
l,
1
<l
2
4
2
−
√
l
for
l
≥
2;
(10.26)
p
l,k
<l
3
/
2
2
k
k
−
1
/
2
4
2
−
√
kl
for
k
=2
,l
≥
88
or
3
≤
k
≤
l/
9
,l
≥
21;
(10.27)
7
20
l
2
−
5
k
+
1
7
l
15
/
4
2
l/
2
−
2
k
+12
2
−
l/
4
−
3
k
p
l,k
<
·
·
l
·
(10.28)
for
l/
9
≤ k ≤ l/
4
,l≥
21;
p
l,k
<
1
7
l
15
/
4
2
−
l/
2
−
2
k
for
k
≥
l/
4
,l
≥
21
.
(10.29)
10
In [BCGP] it is mentioned that Knuth's assertion holds only because the probability of error
for most composite numbers is significantly less than one-fourth; otherwise, the error bound
given by Knuth would lie significantly above the given number.
