与米勒·拉宾 (Miller Rabin) 一起寻找素数
Finding a prime with Miller Rabin
我认为使用 Lua 可以正确实现 miller-rabin 算法,并且我正在尝试为素数获得一致的 return。看来我的实现只有一半的时间有效。尽管如果我尝试在 python 中实现类似的代码,该代码在 100% 的时间内都能正常工作。有人能给我指出正确的方向吗?
--decompose n-1 as (2^s)*d
local function decompose(negOne)
exponent, remainder = 0, negOne
while (remainder%2) == 0 do
exponent = exponent+1
remainder = remainder/2
end
assert((2^exponent)*remainder == negOne and ((remainder%2) == 1), "Error setting up s and d value")
return exponent, remainder
end
local function isNotWitness(n, possibleWitness, exponent, remainder)
witness = (possibleWitness^remainder)%n
if (witness == 1) or (witness == n-1) then
return false
end
for _=0, exponent do
witness = (witness^2)%n
if witness == (n-1) then
return false
end
end
return true
end
--using miller-rabin primality testing
--n the integer to be tested, k the accuracy of the test
local function isProbablyPrime(n, accuracy)
if n <= 3 then
return n == 2 or n == 3
end
if (n%2) == 0 then
return false
end
exponent, remainder = decompose(n-1)
--checks if it is composite
for i=0, accuracy do
math.randomseed(os.time())
witness = math.random(2, n - 2)
if isNotWitness(n, witness, exponent, remainder) then
return false
end
end
--probably prime
return true
end
if isProbablyPrime(31, 30) then
print("prime")
else
print("nope")
end
Python 具有任意长度的整数。 Lua 没有。
问题出在 witness = (possibleWitness^remainder)%n
.
Lua 无法直接计算 29^15 % 31
的准确结果。
有一种解决方法适用于数字 n < sqrt(2^53)
:
witness = mulmod(possibleWitness, remainder, n)
其中
local function mulmod(a, e, m)
local result = 1
while e > 0 do
if e % 2 == 1 then
result = result * a % m
e = e - 1
end
e = e / 2
a = a * a % m
end
return result
end
我认为使用 Lua 可以正确实现 miller-rabin 算法,并且我正在尝试为素数获得一致的 return。看来我的实现只有一半的时间有效。尽管如果我尝试在 python 中实现类似的代码,该代码在 100% 的时间内都能正常工作。有人能给我指出正确的方向吗?
--decompose n-1 as (2^s)*d
local function decompose(negOne)
exponent, remainder = 0, negOne
while (remainder%2) == 0 do
exponent = exponent+1
remainder = remainder/2
end
assert((2^exponent)*remainder == negOne and ((remainder%2) == 1), "Error setting up s and d value")
return exponent, remainder
end
local function isNotWitness(n, possibleWitness, exponent, remainder)
witness = (possibleWitness^remainder)%n
if (witness == 1) or (witness == n-1) then
return false
end
for _=0, exponent do
witness = (witness^2)%n
if witness == (n-1) then
return false
end
end
return true
end
--using miller-rabin primality testing
--n the integer to be tested, k the accuracy of the test
local function isProbablyPrime(n, accuracy)
if n <= 3 then
return n == 2 or n == 3
end
if (n%2) == 0 then
return false
end
exponent, remainder = decompose(n-1)
--checks if it is composite
for i=0, accuracy do
math.randomseed(os.time())
witness = math.random(2, n - 2)
if isNotWitness(n, witness, exponent, remainder) then
return false
end
end
--probably prime
return true
end
if isProbablyPrime(31, 30) then
print("prime")
else
print("nope")
end
Python 具有任意长度的整数。 Lua 没有。
问题出在 witness = (possibleWitness^remainder)%n
.
Lua 无法直接计算 29^15 % 31
的准确结果。
有一种解决方法适用于数字 n < sqrt(2^53)
:
witness = mulmod(possibleWitness, remainder, n)
其中
local function mulmod(a, e, m)
local result = 1
while e > 0 do
if e % 2 == 1 then
result = result * a % m
e = e - 1
end
e = e / 2
a = a * a % m
end
return result
end