通过生成素数使用QuickCheck

Question

背景资料

为了好玩，我试图编写一个快速检查的属性，可以测试背后的基本思想 RSA密码学.

• 选择两个不同的素数, 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 是"信息"，将其提升到 eth电源模块 N 是"编码"消息的行为，并将编码的消息提升到 dth电源模块 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

（谢谢，谷歌和随机博客，为 模块化乘法逆的实现)

问题

问题应该很明显:属性上有太多的条件使其完全可用。试图调用 quickCheck prop_rsa 在ghci使我的终端挂起。

所以我到处找 快速检查手册 有点，上面写着:

属性可以采用以下形式

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

我如何做一个 <generator> 对于素数？或与其他约束，使得 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兼容的素数生成器（窃取Eratosthenes实现的筛子 http://en.literateprograms.org/Sieve_of_Eratosthenes_（哈斯克尔)):

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) 在你的财产里。