Cryptography Reference
In-Depth Information
1. The Fermat test to base 2 given by the previously defined function
Fermat2
Test
.
2. The Fibonacci test for numbers
≡±
2
(
mod 5
)
:
> FibonacciTest := n -> (evalb(n mod 5 = 2) or evalb(n mod 5 = 3)) and
evalb(combinat:-fibonacci(n+1) mod n = 0):
Then the 'PSW test' would be:
> PSWTest := n -> Fermat2Test(n) and FibonacciTest(n):
We leave winning the $620 as a (not easy!) exercise:
Exercise 6.12
(i) Download the text file called
primes620.txt
from
(ii) Read this text file as a Maple list consisting of 2030 primes.
(iii) Construct a suitable (big) list of composite numbers by multiplying appropriate
subsets of these primes.
(iv) Try to find a solution by applying the function
PSWTest
to the members of
this list ...
The probabilistic primality tests (or compositeness tests) mentioned so far are
the ones commonly used to select primes for cryptographic use but there are also
deterministic tests that, while less efficient, provide also a proof of the primality of
the numbers that are declared prime. One of the more powerful is CPP ("Cyclotomy
Primality Proving", also called the Jacobi sum test, [52, 60]) whose running time
is
O
c
ln ln ln
n
for some constant
c
. Although this is not polynomial time, the
functionlnlnln
n
grows very slowly (its value is about 5 when
n
has five million
decimal digits) and, for all practical purposes, it behaves as if it were bounded.
Because of this it is sometimes said that the algorithm runs in
superpolynomial time
and it has been used to obtain primality proofs of primes of several thousand decimal
digits.
An alternative test which is expected to be asymptotically more efficient is ECPP
(“Elliptic Curve Primality Proving”) based on the arithmetic of elliptic curves which,
heuristically, runs in
expected polynomial time O
((
ln
n
)
)
ln
5
+
ε
n
using fast multiplication
techniques. This is a probabilistic Las Vegas algorithmwhich always gives the correct
result but the running time could be much larger than the above estimate on some
inputs (and, moreover, the expected running time has not been rigorously proved).
However, the test works very well in practice and has the additional advantage of
providing a
certificate
that permits the primality to be checked much more quickly. A
distributed version of ECPP due toMorain [146] has been used to prove the primality
of some very large primes, and there is also a nice version of ECPP for Windows
operating systems due to Martin [137].
None of the preceding algorithms for primality testing provides an answer to a
problem that remained open for many years: is there a deterministic polynomial-time
algorithm for testing the primality of an integer?
(
)
