Cryptography Reference
In-Depth Information
From these inequalities we can calculate what probabilities we can get below
with how many passes of the Miller-Rabin test for a given number of digits, or how
many passes are necessary to get below given probabilities of error. The results
are far below those of Rabin, according to whom
k
repetitions are necessary to
reach a probability of error beneath
4
−
k
. Table 10-3 shows values of
k
necessary
to reach probabilities below
2
−
80
and
2
−
100
as a function of the number
l
of
binary digits of the numbers being tested.
Table 10-3. The number
k
of passes through the Miller-Rabin test to achieve
probabilities of error less than
2
−
80
and
2
−
100
as a function of the number
l
of binary
digits (after [DaLP]).
Probability
<
2
−
80
Probability
<
2
−
100
l
k
l
k
49
37
49
47
73
32
73
42
105
25
105
35
137
19
132
29
197
15
198
23
220 to 234
13
223
20
235 to 251
12
242
18
252 to 272
11
253
17
273 to 299
10
265
16
300 to 331
9
335
12
332 to 374
8
480 to 542
8
375 to 432
7
543 to 626
7
433 to 513
6
627 to 746
6
514 to 637
5
747 to 926
5
638 to 846
4
927 to 1232
4
847 to 1274
3
1233 to 1853
3
1275 to 2860
2
1854 to 4095
2
≥
2861
1
≥
4096
1
The effect of using the division sieve before the Miller-Rabin test is not
considered in inequalities (10.26) through (10.29). Since the sieve greatly
reduces the relative frequency of composite candidates, one may expect that the
probabilities of error for a given choice of
l
and
k
would be further reduced.
