Miller–Rabin primality test: Difference between revisions
Content added Content deleted
| Line 922: | Line 922: | ||
% and augmented number of deterministic proving bases. |
% and augmented number of deterministic proving bases. |
||
% Deleted first_1000/0 because not used. |
% Deleted first_1000/0 because not used. |
||
% Modified, January 26, 2014 @ |
% Modified, January 26, 2014 @ 11:04am PST. |
||
is_prime(1) -> false; |
is_prime(1) -> false; |
||
| Line 955: | Line 955: | ||
is_mr_prime(N, As) when N>2, N rem 2 == 1 -> |
is_mr_prime(N, As) when N>2, N rem 2 == 1 -> |
||
{D, S} = find_ds(N), |
{D, S} = find_ds(N), |
||
%% this is a test for compositedness; the first two case patterns disprove |
|||
%% compositedness, while the third proves compositedness and thereby |
|||
%% foreshortens some searches while increasing execution time for others |
|||
not lists:any(fun(A) -> |
not lists:any(fun(A) -> |
||
case mr_series(N, A, D, S) of |
case mr_series(N, A, D, S) of |
||
[1|_] -> false; |
[1|_] -> false; |
||
L -> not lists:member(N-1, L); |
L -> not lists:member(N-1, L); |
||
[_|T] -> lists:member(1, T) |
[_|T] -> lists:member(1, T) |
||
end |
end |
||
end, |
end, |
||