Cryptography Reference
In-Depth Information
> select(Fermat2Pseudoprime, [seq(2*i-1, i=2..5000)]);
[341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033,
4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911]
We see that there are only 22 2-pseudoprimes below 10000, while the number of
primes in this range is:
> numtheory:-pi(10000);
1229
In order to make more meaningful comparisons between the number of primes
and the number of pseudoprimes, we may use the following counting function, which
takes as input an integer range and the name of a Maple Boolean-valued procedure,
and returns the number of odd integers in the range for which the procedure returns
true
.
> count := proc(range::(integer .. integer), func::name)
local s, e, count, 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;
count := 0;
for i from s by 2 to e do
if func(i) then
count := count+1
end if
end do;
count
end proc:
For example, we may compare the number of 2-pseudoprimes to the number of
primes in the interval
10
8
10
8
10
7
[
,
+
]
as follows:
> map(x-> count(10ˆ8 .. 10ˆ8+10ˆ7, x), ['Fermat2Pseudoprime', 'isprime']);
[94, 541854]
The first of these integers is the number of 2-pseudoprimes and the second is
the number of primes. There is already a remarkable difference between the two
numbers—there are almost 6000 primes in the interval for each 2-pseudoprime—
but we are going to do a more complete experiment to appreciate how the number
of 2-pseudoprimes in a fixed-length interval varies when we double the size of the
involved numbers. For this computation it will be convenient to modify the above
function
count
in order to avoid applying
isprime
twice to each odd number (one
when computing the number of primes and the other when computing the number
of 2-pseudoprimes). So we will build a function called
TestError
that computes,
for a given interval, the number of odd integers that pass a test given by a Maple
function
func
(in the case we are interested,
Fermat2Test
) and also the number
of primes in the interval, as well as the probability that an integer chosen at random
in the interval that passes the test given by
func
is composite (i.e., the probability
of error of the test
func
in the given interval).
