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

-------------------------------------------}