2
我在Haskell中實現了Miller Rabin測試。我試圖嚴格遵循例如在米勒拉賓測試的維基百科條目中給出的僞代碼。現在我在網上發現,對於某些證人選擇,測試是確定性的,達到某個給定的界限。我對2^64以下的素數感興趣,所以我在這篇文章中找到了足夠的界限。然而,該代碼似乎適用於我測試過的大多數小素數,但對於一些較大的素數則失敗。例如,我嘗試了十位數的素數5915587277,測試返回false。我認爲我的實施是正確的,但希望有人能夠發現我犯了一個錯誤,並誤解了有關MR測試的情況。預先感謝您的幫助。另外,對於凌亂的代碼感到抱歉。爲什麼我的米勒拉賓算法不起作用(Haskell)?
isPrime :: Int -> Bool
isPrime n = millerRabinTest n (factorizeN (n-1))
{- factorizeN finds a number s and odd number d such that n -1 = (2^s)d by
succesively dividing n by two if it is even. -}
factorizeN :: Int -> (Int, Int)
factorizeN n = fN n 0
where
fN n s | even n = fN (n `div` 2) (s + 1)
| otherwise = (n,s)
{- this is the main function. it takes w values from a set of witnesses
and checks if n passes the test. If it doesn't, n is not prime, if it does
for all w, it is probably prime. -}
millerRabinTest :: Int -> (Int,Int) -> Bool
millerRabinTest n (d,s) = and [test n (expmod w d n) s | w <- onesToCheck]
{- this is the test that is used in the millerRabinTest function. it sees if
w^d = 1 mod n or n-1 mod n, if not it multiplies by two
and checks again for a total of s-1 times. If it is never true then the number
is not prime -}
test :: Int -> Int -> Int -> Bool
test n w s | w `elem` [1,n-1] = True
| otherwise = or [ (expmod w (2^k) n) `elem` [1,n-1]| k <- [1..s]]
{- set of witnesses that should make the Miller Rabin test deterministic if
n < 2^64. -}
onesToCheck :: [Int]
onesToCheck = [2,325,9375,28178,450775,9780504,1795265022]
{- function that calculates a^e mod n. -}
expmod :: Int -> Int -> Int -> Int
expmod a e n | e == 1 = a `mod` n
| (e `mod` 2) == 0 = (expmod ((a*a) `mod` n) (e `div` 2) n)
| otherwise = (a*(expmod ((a*a) `mod` n) (e `div` 2) n)) `mod` n
非常感謝,這個作品非常完美。 – Slugger 2014-09-20 12:19:50