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

既製の高速素数性テストは、現在の最先端技術であるベイリーPSWテストを含むarithmoiパッケージで見つけることができます。次に、モジュールをインポートするだけで、上記のコードがすぐに機能するはずです。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 に答える