Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (Removed reference to Erlang because the Erlang version is too different, whereas the Prolog version was the model used.) |
(Mercury: minor format edit. Oz: added the language.) |
||
| Line 1,879: | Line 1,879: | ||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
||
<lang Mercury> |
<lang Mercury> |
||
These were compiled using Mercury 14.01.1 and are adapted from |
These were compiled using Mercury 14.01.1 and are adapted from |
||
| Line 2,105: | Line 2,103: | ||
</lang> |
</lang> |
||
=={{header|Oz}}== |
|||
<lang Oz> |
|||
The following is adapted from the Prolog and Mercury versions. |
|||
%--------------------------------------------------------------------------% |
|||
% module: Primality |
|||
% file: Primality.oz |
|||
% version: 17 DEC 2014 @ 6:50AM |
|||
%--------------------------------------------------------------------------% |
|||
declare |
|||
%--------------------------------------------------------------------------% |
|||
fun {IsPrime N} % main interface of module |
|||
if N < 2 then false |
|||
elseif N < 4 then true |
|||
elseif (N mod 2) == 0 then false |
|||
elseif N < 341330071728321 then {IsMRprime N {DetWit N}} |
|||
else {IsMRprime N {ProbWit N 20}} |
|||
end |
|||
end |
|||
%--------------------------------------------------------------------------% |
|||
fun {DetWit N} % deterministic witnesses |
|||
if N < 1373653 then [2 3] |
|||
elseif N < 9080191 then [31 73] |
|||
elseif N < 25326001 then [2 3 5] |
|||
elseif N < 3215031751 then [2 3 5 7] |
|||
elseif N < 4759123141 then [2 7 61] |
|||
elseif N < 1122004669633 then [2 13 23 1662803] |
|||
elseif N < 2152302898747 then [2 3 5 7 11] |
|||
elseif N < 3474749660383 then [2 3 5 7 11 13] |
|||
elseif N < 341550071728321 then [2 3 5 7 11 13 17] |
|||
else nil |
|||
end |
|||
end |
|||
%--------------------------------------------------------------------------% |
|||
fun {ProbWit N K} % probabilistic witnesses |
|||
local A B C in |
|||
A = 6364136223846793005 |
|||
B = 1442695040888963407 |
|||
C = N - 2 |
|||
{RWloop N A B C K nil} |
|||
end |
|||
end |
|||
fun {RWloop N A B C K L} |
|||
local N1 in |
|||
N1 = (((N * A) + B) mod C) + 1 |
|||
if K == 0 then L |
|||
else {RWloop N1 A B C (K - 1) N1|L} |
|||
end |
|||
end |
|||
end |
|||
%--------------------------------------------------------------------------% |
|||
fun {IsMRprime N As} % the Miller-Rabin algorithm |
|||
local D S T Ts in |
|||
{FindDS N} = D|S |
|||
{OuterLoop N As D S} |
|||
end |
|||
end |
|||
fun {OuterLoop N As D S} |
|||
local A At Base C in |
|||
As = A|At |
|||
Base = {Powm A D N} |
|||
C = {InnerLoop Base N 0 S} |
|||
if {Not C} then false |
|||
elseif {And C (At == nil)} then true |
|||
else {OuterLoop N At D S} |
|||
end |
|||
end |
|||
end |
|||
fun {InnerLoop Base N Loop S} |
|||
local NextBase NextLoop in |
|||
NextBase = (Base * Base) mod N |
|||
NextLoop = Loop + 1 |
|||
if {And (Loop == 0) (Base == 1)} then true |
|||
elseif Base == (N - 1) then true |
|||
elseif NextLoop == S then false |
|||
else {InnerLoop NextBase N NextLoop S} |
|||
end |
|||
end |
|||
end |
|||
%--------------------------------------------------------------------------% |
|||
fun {FindDS N} |
|||
{FindDS1 (N - 1) 0} |
|||
end |
|||
fun {FindDS1 D S} |
|||
if (D mod 2 == 0) then {FindDS1 (D div 2) (S + 1)} |
|||
else D|S |
|||
end |
|||
end |
|||
%--------------------------------------------------------------------------% |
|||
fun {Powm A D N} % returns (A ^ D) mod N |
|||
if D == 0 then 1 |
|||
elseif (D mod 2) == 0 then {Pow {Powm A (D div 2) N} 2} mod N |
|||
else (A * {Powm A (D - 1) N}) mod N |
|||
end |
|||
end |
|||
%--------------------------------------------------------------------------% |
|||
% end_module Primality |
|||
</lang> |
|||