素数を生成して QuickCheck を使用する

Question

背景

楽しみのために、背後にある基本的なアイデアをテストできるクイックチェック用のプロパティを作成しようとしています。 RSA による暗号化.

• 2 つの異なる素数を選択し、 p そして q.
• させて N = p*q
• e 何かの数字です 比較的プライム に (p-1)(q-1) (実際には、高速エンコードの場合、e は通常 3 です)
• d それは モジュラーインバース の e モジュロ (p-1)(q-1)

すべてのために x そのような 1 < x < N, 、それは常に真実です (x^e)^d = x modulo N

言い換えると、 x は「メッセージ」であり、 e番目のパワーモッド N メッセージを「エンコード」し、エンコードされたメッセージを d番目のパワーモッド N それを「デコード」する行為です。

(この性質は次の場合にも自明に当てはまります x = 1, 、独自の暗号化である場合）

コード

これまでにコード化したメソッドは次のとおりです。

import Test.QuickCheck

-- modular exponentiation
modExp :: Integral a => a -> a -> a -> a
modExp y z n = modExp' (y `mod` n) z `mod` n
    where modExp' y z | z == 0 = 1
                      | even z =  modExp (y*y) (z `div` 2) n
                      | odd z  = (modExp (y*y) (z `div` 2) n) * y

-- relatively prime
rPrime :: Integral a => a -> a -> Bool
rPrime a b = gcd a b == 1

-- multiplicative inverse (modular)
mInverse :: Integral a => a -> a -> a
mInverse 1 _ = 1
mInverse x y = (n * y + 1) `div` x
    where n = x - mInverse (y `mod` x) x

-- just a quick way to test for primality
n `divides` x = x `mod` n == 0
primes = 2:filter isPrime [3..]
isPrime x = null . filter (`divides` x) $ takeWhile (\y -> y*y <= x) primes

-- the property
prop_rsa (p,q,x) = isPrime p  &&
                   isPrime q  &&
                   p /= q     &&
                   x > 1      &&
                   x < n      &&
                   rPrime e t ==>
                   x == (x `powModN` e) `powModN` d
    where e = 3
          n = p*q
          t = (p-1)*(q-1)
          d = mInverse e t
          a `powModN` b = modExp a b n

(Google とランダムなブログ、ありがとう 逆モジュラー乗算の実装)

質問

問題は明らかであるはずです。物件には条件が多すぎて、まったく使用できません。呼び出そうとしています quickCheck prop_rsa ghci で端末がハングしました。

それで私は調べてみました クイックチェックマニュアル 少しすると、こう書かれています。

プロパティは次の形式をとることがあります。

forAll <generator> $ \<pattern> -> <property>

どうやって作るのですか <generator> 素数の場合は？または、他の制約を使用すると、 quickCheck 多数の失敗した条件を選別する必要はありませんか?

その他の一般的なアドバイス (特に QuickCheck に関する) は大歓迎です。

Answer 1

さて、これが私がやったことです。

ファイルの先頭

{-# LANGUAGE NoMonomorphismRestriction #-}

import Test.QuickCheck
import Control.Applicative

prop_rsa を除く、質問に記載されているすべてのコード。これは (明らかに) 大幅に変更されました。

prop_rsa = forAll primePair $ \(p,q) ->
           let n = p*q
           in forAll (genUnder n) $ \x  ->
              let e = 3
                  t = (p-1)*(q-1)
                  d = mInverse e t
                  a `powModN` b = modExp a b n
              in p /= q &&
                 rPrime e t ==>
                 x == (x `powModN` e) `powModN` d

のタイプ primePair は Gen (Int, Int), 、およびタイプ genUnder は Int -> Gen Int. 。何が魔法の背後にあるのか正確にはわかりません forAll しかし、私はこれが正しいと確信しています。1) 条件を間違えると失敗するようにする、2) ネストされていることを確認する、というアドホックな調整をいくつか行いました。 forAll の値を変化させています x テストケース全体で。

そこで、これらのジェネレーターを作成する方法を次に示します。あることに気づいたら <generator> ドキュメントでは、単に何らかのタイプのことを意味していました Gen a, 、ケーキでした。

genNonzero = (\x -> if x == 0 then 1 else x) `fmap` arbitrary
genUnder :: Int -> Gen Int
genUnder n = ((`mod` n) . abs) `fmap` genNonzero

genSmallPrime = ((\x -> (primes !! (x `mod` 2500))) . abs) `fmap` arbitrary

primePair :: Gen (Int, Int)
primePair = (,) <$> genSmallPrime <*> genSmallPrime

primePair 正しく理解するまでに試行錯誤が必要でした。一部のコンビネータがそのようなものであることは知っていました すべき 仕事はしていますが、まだそこまで詳しくありません fmap, <$> そして <*> 私がなりたいように。最初の 2500 個の素数の中からのみ選択するように計算を制限しました。それ以外の場合は、生成に永遠にかかる非常に大きなものを選択したかったようです。

偶然の注意点

怠惰のおかげで、 d = mInverse e t 条件が満たされない限り計算されません。条件がいつになるかは未定義なので、これは良いことです。 rPrime e t は誤りです。英語では整数 a 次の場合にのみ乗法逆数 (mod b) があります。 a そして b 比較的プライムです。

Answer 2

ここでは、QuickCheck 互換の素数ジェネレーターを作成する 1 つの方法を示します (エラトステネスのふるいの実装を盗用します)。 http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)):

import Test.QuickCheck

newtype Prime = Prime Int deriving Show

primes = sieve [2..]
    where
      sieve (p:xs) = Prime p : sieve [x | x <- xs, x `mod` p > 0]

instance Arbitrary Prime where
    arbitrary = do i <- arbitrary
                   return $ primes!!(abs i)

QuickCheck では次のように使用できます。

prop_primes_dont_divide (Prime x) (Prime y) = x == y || x `mod` y > 0

あなたの使用のために、あなたは置き換えます p そして q と (Prime p) そして (Prime q) あなたの所有地で。