Cryptography Reference
In-Depth Information
We use
isprime
in order to count the primes but this function is not guaranteed
to always give the correct result: in theory, it might happen that some composite
could be declared prime by
isprime
although no such example has been found so
far. Even if this were to happen, the deviation would be so small that its effect would
be negligible but, anyway, it is known that the output of
isprime
is always correct
for numbers below 10
15
such as those we will use in our experiment.
The function
TestError
takes as input an integer range,
range
, and a func-
tion name,
func
, for a Boolean-valued Maple function acting on integers. The
output is a list of three elements, the first of which is the number of odd inte-
gers in the given interval that pass the test
func
. The second element of this list
is the number of primes in the interval and, finally, the last element is equal to
Pr
whenever
func
is a function that returns
true
when applied to primes and
n
is randomly chosen among the odd integers in
the interval defined by
range
.
(
n
is composite
|
func(n) = true
)
> TestError := proc(range::(integer .. integer), func::name)
local s, e, count1, count2, i;
s := op(range)[1];
if type(s, even) then
s:=s+1
end if;
e := op(range)[2];
if type(e, even) then
e:=e-1
end if;
count1 := 0;
count2 := 0;
for i from s by 2 to e do
if isprime(i) then
count1 := count1+1
elif func(i) then
count2 := count2+1
end if
end do;
[count2, count1, evalf(count2/(count1+count2))]
end proc:
Next we use this function to compute the probability of error of the Fermat test
to base 2 when the integer is randomly chosen in any of two intervals of length 2
28
,
the first consisting of 32-bit integers and the second consisting of 48-bit integers.
> TestError(2ˆ31 .. 2ˆ31+2ˆ28, Fermat2Test);
TestError(2ˆ47 .. 2ˆ47+2ˆ28, Fermat2Test);
[382, 12457225, 0.00003066399510]
[0, 8237902, 0.]
In these lists, the first element is the number of 2-pseudoprimes in the interval,
the second is the number of primes, and the third is the probability that a randomly
chosen integer in the interval that passes the Fermat base-2 test is composite. We see
that, as was to be expected because of the PNT, the number of primes in the 48-bit
interval is approximately two-thirds of the number of primes in the 32-bit interval. In
contrast, the number of 2-pseudoprimes decreases much faster and, consequently, the
probability of error of the Fermat test to base 2 decreases dramatically as the size of
the numbers increases (and these numbers are still much too small for cryptographic
use). Indeed, while there are over 8million primes among the first 2
28
48-bit numbers,
