

 This page uses content from Wikipedia. The original article was at Miller–Rabin primality test. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not.

The algorithm, as modified by Michael O. Rabin to avoid the generalized Riemann hypothesis, is a probabilistic algorithm.

The pseudocode, from Wikipedia is:

Input: n > 2, an odd integer to be tested for primality;
       k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
   pick a randomly in the range [2, n − 1]
   x ← ad mod n
   if x = 1 or x = n − 1 then do next LOOP
   repeat s − 1 times:
      x ← x2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next LOOP
   return composite
return probably prime

 The nature of the test involves big numbers, so the use of "big numbers" libraries (or similar features of the language of your choice) are suggested, but not mandatory.
 Deterministic variants of the test exist and can be implemented as extra (not mandatory to complete the task)


 
%--------------------------------------------------------------------------%
% 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
 
 