3

我刚进入haskell。我正在尝试编写一个质数生成器，它会根据我给它的位数返回一个质数。我是否使用某种埃拉托色尼筛？这会是最快的方法吗？目前，我已经有一个 Miller-Rabin 的素数检查器。有正确的方法和错误的方法吗？此外，我希望能够非常快速地生成大量数据。

前任。生成一个 32 位的素数

genp 32

代码到此为止。

import System.IO
import System.Random
import Data.List
import Control.Monad
import Control.Arrow


primesTo100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

powerMod :: (Integral a, Integral b) => a -> a -> b -> a
powerMod m _ 0 =  1
powerMod m x n | n > 0 = join (flip f (n - 1)) x `rem` m where
  f _ 0 y = y
  f a d y = g a d where
    g b i | even i    = g (b*b `rem` m) (i `quot` 2)
          | otherwise = f b (i-1) (b*y `rem` m)

witns :: (Num a, Ord a, Random a) => Int -> a -> IO [a]
witns x y = do
     g <- newStdGen 
     let r = [9080191, 4759123141, 2152302898747, 3474749600383, 341550071728321]
         fs = [[31,73],[2,7,61],[2,3,5,7,11],[2,3,5,7,11,13],[2,3,5,7,11,13,17]]
     if  y >= 341550071728321
      then return $ take x $ randomRs (2,y-1) g
       else return $ snd.head.dropWhile ((<= y).fst) $ zip r fs

isMillerRabinPrime :: Integer -> IO Bool
isMillerRabinPrime n | n `elem` primesTo100 = return True
                     | otherwise = do
    let pn = pred n
        e = uncurry (++) . second(take 1) . span even . iterate (`div` 2) $ pn
        try = return . all (\a -> let c = map (powerMod n a) e in
                                  pn `elem` c || last c == 1)
    witns 100 n >>= try



type Prime = Integer

isProbablyPrime :: Prime -> Bool
isProbablyPrime n = isMillerRabinPrime n

pickFirstFrom :: Integer -> Prime
pickFirstFrom n = head $ filter isProbablyPrime [n..]

numBits = 1024
constantStdGen = mkStdGen 1234567 -- a random number

randomByBits n = fst $ randomR (2^(n-1), 2^n-1) constantStdGen

answer = pickFirstFrom (randomByBits numBits)

将库函数与 RSA 一起使用：

import Control.Monad.Fix 
import Math.NumberTheory.Primes

rndPrime :: Int -> IO Integer
rndPrime bits =
    fix $ \again -> do
        x <- fmap (.|. 1) $ randomRIO (2^(bits - 1), 2^bits - 1)
        if isPrime x then return x else again

rndPrimes :: Int -> IO (Integer, Integer)
rndPrimes bits = do
    p <- rndPrime bits
    fix $ \again -> do
        q <- rndPrime bits
        if p /= q then return (p, q) else again

谢谢大家，我真的很感谢你的帮助。

4

2 回答 2

16

为了生成特定位大小的奇数随机素数，实际上有这种方法，假设（通常是概率）素性测试isPrime：

rndPrime :: Int -> IO Integer
rndPrime bits =
    fix $ \again -> do
        x <- fmap (.|. 1) $ randomRIO (2^(bits - 1), 2^bits - 1)
        if isPrime x then return x else again

对于 RSA：

rndPrimes :: Int -> IO (Integer, Integer)
rndPrimes bits = do
    p <- rndPrime bits
    fix $ \again -> do
        q <- rndPrime bits
        if p /= q then return (p, q) else again

您可以在arithmoi包中找到现成的快速素性测试，包括当前最先进的Baillie PSW 测试。然后只需导入Math.NumberTheory.Primes模块，上面的代码就可以开箱即用了。

于 2012-11-09T03:17:01.670 回答
2

你很幸运，先生。素数出现得如此频繁，以至于您可以尝试从给定的起始数字枚举所有数字并选择第一个是素数的数字。

解决方案是这样的

import System.Random

type Prime = Integer

isProbablyPrime :: Prime -> Bool
isProbablyPrime n = error "insert miller rabin here"

pickFirstFrom :: Integer -> Prime
pickFirstFrom n = head $ filter isProbablyPrime [n..]

numBits = 1024
constantStdGen = mkStdGen 1234567 -- a random number

randomByBits n = fst $ randomR (2^(n-1), 2^n-1) constantStdGen

answer = pickFirstFrom (randomByBits numBits)

这answer将是您在评论中指定的。但是请注意，您必须修改此代码以允许多个常量种子！

于 2012-11-09T01:27:26.630 回答