%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  NAME :
%      primal_testing.pl
%
% VERSION :
%     0
%
% AUTHOR : Matthieu Petit, Arnaud Gotlieb and Arnaud Jobin
%
% FUNCTION :
%      Implementation of a weakest form of Miller-Rabin prime test
%      
% REMARKS : any problem, contact petit@(without advertissement)irisa.fr
%
% NOTE TO THE USER :  need ctr_proba_v0.pl to work
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%---------------
% Description
%---------------
% Implementation of a weak version
% of Miller-Rabin primal testing test
%----------------



:- multifile clpfd:dispatch_global/4.




primal_testing(N,K) :-
        init_env(Env),
        N in 3..4000000,
        Xmax#=N-1,
        itere(N,Xmax,K,Env),
        fin_env(Env).


itere(_N,_Xmax,0,_Env) :-
        !.


% Default

itere(N,Xmax,K,Env) :-
        choose_range(X,[2,Xmax],'uniform',[fermat_test(X,N)],[no_filtering,lvar([N])],Env),
        K1 is K-1,
        itere(N,Xmax,K1,Env).





% fermat testing

fermat_test(X,N) :-
        clpfd:fd_global(test_ctr(X,N), acc(1,1), [min(N),dom(X)]).

clpfd:dispatch_global(test_ctr(X,N), acc(M,ACC), acc(M1,ACC1), Actions) :-
        test_eval(X, N, M, ACC, M1, ACC1, Actions).

test_eval(X,N, M, ACC, N, ACC1, Actions) :-
        nonvar(N),
        !,
        Actions = [exit, call(user:test_value(M,N, X,N, ACC,ACC1)),ACC1=1].
test_eval(X,N, M,ACC, NMIN, ACC1, Actions) :-
        fd_min(N, NMIN),
        NMIN > M,
        !,
        Actions = [call(user:test_value(M,NMIN, X,N,ACC,ACC1))].
test_eval(_X,_N, M,ACC, M, ACC, Actions) :-
        Actions = [].
                  

% M et N sont "ground"
test_value(N,N,  _X, _N, ACC, ACC) :-
        !.
test_value(M,NMIN, X,N, ACC,ACC1) :-
        ACC_INTER #= (X*ACC) mod N,
        M1 is M+1,
        test_value(M1,NMIN, X,N, ACC_INTER,ACC1).





%---------------
% Request
%--------------
% Funny request: Try :)
% ?- N in 2..335544431,primal_testing(N,20),labeling([],[N]).
%--------------
