Fermat primality test
Package fermat
Import "misc/random".
Import "collect/search".
{--------------------------------------------
(isWitness x n) is true if x is a witness to
the fact that n is not prime. Put another
way, x represents convincing evidence that n
is not prime.
This uses the Fermat's Little Theorem test.
---------------------------------------------}
Let isWitness n x =
x `mod` n =/= 0 and x^(n-1) `mod` n =/= 1
%Let
{---------------------------------------------
(atLeastoneTrue L) is true if list L contains
at least one member that is true.
----------------------------------------------}
Let atLeastOneTrue lst =
someSatisfy idf lst
%Let
{--------------------------------------------
(probablyPrime n) is true if a list of twenty
randomly chosen numbers from the range [1,...,n-1]
does not contain a witness. That is, if we have tested
twenty randomly chosen numbers, and none of them
are witnesses, then we conclude that n is probably prime.
foundWitness is true if there is a witness in the
list. The answer is (not foundWitness).
listOfTwentyRandomNumbers is a list of 20 randomly
chosen numbers in the range from [1,...,n-1]. It uses
a pseudo-random number generator from the misc/random
library.
---------------------------------------------}
Let probablyPrime n = not foundWitness |
Let
listOfTwentyRandomNumbers = [randomRange(1,n-1) | x from [1,...,20]];
testResults = [isWitness n r | r from listOfTwentyRandomNumbers];
foundWitness = atLeastOneTrue testResults
%Let
%Let
{--------------------------------------
Try some numbers.
---------------------------------------}
Execute
For n from [2,...,50] do
Display
n; " "; probablyPrime n; "\n"
%Display
%For
%Execute
%Package
{-------------------------------------------------
Output:
2 true
3 true
4 false
5 true
6 false
7 true
8 false
9 false
10 false
11 true
12 false
13 true
14 false
15 false
16 false
17 true
18 false
19 true
20 false
21 false
22 false
23 true
24 false
25 false
26 false
27 false
28 false
29 true
30 false
31 true
32 false
33 false
34 false
35 false
36 false
37 true
38 false
39 false
40 false
41 true
42 false
43 true
44 false
45 false
46 false
47 true
48 false
49 false
50 false
-------------------------------------------}