```    1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2/*	Nan.Numerics.Prime
3	A simple prime number library
4	Copyright 2016 Julio P. Di Egidio
5	<mailto:julio@diegidio.name>
6	<http://julio.diegidio.name/Projects/Nan.Numerics.Prime/>
7
8	This file is part of Nan.Numerics.Prime.
9
10	Nan.Numerics.Prime is free software: you can redistribute it and/or modify
12	the Free Software Foundation, either version 3 of the License, or
13	(at your option) any later version.
14
15	Nan.Numerics.Prime is distributed in the hope that it will be useful,
16	but WITHOUT ANY WARRANTY; without even the implied warranty of
17	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18	GNU General Public License for more details.
19
20	You should have received a copy of the GNU General Public License
21	along with Nan.Numerics.Prime.  If not, see <http://www.gnu.org/licenses/>.
22*/

23%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
24
25% (SWI-Prolog 7.3.25)
26
27% TODO: Implement test error estimates?
28% TODO: Implement option for num. of iterations?
29
30:- module(prime_prb, []).
31
32:- public
33	test_/2,		% +N:posint, -Cert:boolean
34	det_max_/1,		% -Max:posint
35	prb_mul_/1.		% -Mul:posint
```

# A simple prime number library :: probabilistic

Module `prime_prb` provides low-level predicates to test candidate primality of numbers based on a probabilistic primality test.

Implements a variant of the Miller-Rabin primality test that is deterministic for numbers up to `3317044064679887385961980`, otherwise it is probabilistic with the number of iterations fixed at `20`.

NOTE: Predicates in this module are not meant for public use.

author
- Julio P. Di Egidio
version
- 1.2.5-beta
- GNU GPLv3
To be done
- Implement test error estimates?
- Implement option for num. of iterations? */
```   56:- use_module(library(random)).
57
58%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
```
test_(+N:posint, -Cert:boolean) is semidet
True if N is a candidate prime number.

Cert is `true` if N is certainly prime, otherwise it is `false`.

```   66test_(2, true) :- !.
67test_(N, Cert) :-
68	N > 2,
69	test_as_(N, As, Cert),
70	\+ comp_as_(N, As).
71
72test_as_(N, As, true) :-
73	det_as_(N, As), !.
74test_as_(N, As, false) :-
75	prb_as_(N, As).
76
77%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
78
79%	comp_as_(+N:posint +As:list(prime)) is semidet.
80
81comp_as_(N, As) :-
82	calc_n0sd_(N, N0, S0, D),
83	comp_as_(As, N0, S0, D).
84
85comp_as_([A| _], N0, S0, D) :-
86	comp_a_(A, N0, S0, D), !.
87comp_as_([_| As], N0, S0, D) :-
88	comp_as_(As, N0, S0, D).
89
90comp_a_(A, N0, S0, D) :-
91	X is powm(A, D, N0 + 1),
92	X =\= 1, X =\= N0,
93	forall(
94		between(1, S0, R),
95		(	D2 is 1 << R,
96			X2 is powm(X, D2, N0 + 1),
97			X2 =\= N0
98		)
99	).
100
101calc_n0sd_(N, N0, S0, D) :-
102	N0 is N - 1,
103	calc_n0sd___do(N0, 0, S, D),
104	S0 is S - 1.
105
106calc_n0sd___do(N0, A0, S, D) :-
107	N0 /\ 1 =:= 0, !,
108	N1 is N0 >> 1,
109	A1 is A0 + 1,
110	calc_n0sd___do(N1, A1, S, D).
111calc_n0sd___do(D, S, S, D).
112
113%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
```
det_max_(-Max:posint) is det
Max is the maximum number for which the test is deterministic.
```  119det_max_(3317044064679887385961980).
```
prb_mul_(-Mul:posint) is det
Mul is the number of iterations for the probabilistic test.
```  125prb_mul_(20).						% TODO: Review this. ####
126
127%	prb_as_(+N:posint, -As:list(prime)) is semidet.
128
129prb_as_(N, As) :-
130	N2 is N - 2,
131	findall(A,
132	(	between(1, 20/*mul*/, _),
133		random(2, N2, A)
134	), As).
135
136%	det_as_(+N:posint, -As:list(prime)) is semidet.
137
138det_as_(N, As) :-
139	det_sas_(Max, As), N < Max, !.
140
141det_sas_(2047, [2]).
142det_sas_(1373653, [2, 3]).
143det_sas_(25326001, [2, 3, 5]).
144det_sas_(3215031751, [2, 3, 5, 7]).
145det_sas_(2152302898747, [2, 3, 5, 7, 11]).
146det_sas_(3474749660383, [2, 3, 5, 7, 11, 13]).
147det_sas_(341550071728321, [2, 3, 5, 7, 11, 13, 17]).
148det_sas_(3825123056546413051, [2, 3, 5, 7, 11, 13, 17, 19, 23]).
149det_sas_(318665857834031151167461, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]).
150det_sas_(3317044064679887385961981, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]).
151
152%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
```