Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(Add BQN) |
No edit summary |
||
Line 3,340: | Line 3,340: | ||
End Function |
End Function |
||
</lang> |
</lang> |
||
=={{header|Lua}}== |
|||
This implementation of the Miller-Rabin probabilistic primality test is based on the treatment in Chapter 10 of "A Computational Introduction to Number Theory and Algebra" by Victor Shoup. |
|||
<lang lua> function MRIsPrime(n, k) |
|||
-- If n is prime, returns true (without fail). |
|||
-- If n is not prime, then returns false with probability ≥ 4^(-k), true otherwise. |
|||
-- First, deal with 1 and multiples of 2. |
|||
if n == 1 then |
|||
return false |
|||
elseif n == 2 then |
|||
return true |
|||
elseif n%2 == 0 then |
|||
return false |
|||
end |
|||
-- Now n is odd and greater than 1. |
|||
-- Find the unique expression n = 1 + t*2^h for n, where t is odd and h≥1. |
|||
t = (n-1)/2 |
|||
h = 1 |
|||
while t%2 == 0 do |
|||
t = t/2 |
|||
h = h + 1 |
|||
end |
|||
for i = 1, k do |
|||
-- Generate a random integer between 1 and n-1 inclusive. |
|||
a = math.random(n-1) |
|||
-- Test whether a is an element of the set L, and return false if not. |
|||
if not IsInL(n, a, t, h) then |
|||
return false |
|||
end |
|||
end |
|||
-- All generated a were in the set L; thus with high probability, n is prime. |
|||
return true |
|||
end |
|||
function IsInL(n, a, t, h) |
|||
local b = PowerMod(a, t, n) |
|||
if b == 1 then |
|||
return true |
|||
end |
|||
for j = 0, h-1 do |
|||
if b == n-1 then |
|||
return true |
|||
elseif b == 1 then |
|||
return false |
|||
end |
|||
b = (b^2)%n |
|||
end |
|||
return false |
|||
end |
|||
function PowerMod(x, y, m) |
|||
-- Computes x^y mod m. |
|||
local z = 1 |
|||
while y > 0 do |
|||
if y%2 == 0 then |
|||
x, y, z = (x^2)%m, y//2, z |
|||
else |
|||
x, y, z = (x^2)%m, y//2, (x*z)%m |
|||
end |
|||
end |
|||
return z |
|||
end </lang> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |