haskell - 通过生成素数使用 QuickCheck

Question

背景
为了好玩，我正在尝试编写一个用于快速检查的属性，以测试 cryptography with RSA 背后的基本思想。 .

选择两个不同的素数，p和 q .

让 N = p*q

e是某个数字relatively prime至(p-1)(q-1) (实际上，对于快速编码，e 通常为 3)

d是 modular inverse的 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 和随机博客提供 implementation of modular multiplicative inverse )
问题
问题应该很明显:该属性的条件太多，无法使其完全可用。试图调用 quickCheck prop_rsa在 ghci 中使我的终端挂起。
所以我戳了一下 QuickCheck manual一点，它说:

Properties may take the form

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

如何制作 <generator>对于素数？或与其他约束条件，使 quickCheck不必筛选一堆失败的条件？
欢迎任何其他一般性建议(尤其是关于 QuickCheck)。

Answer 1

这是制作兼容 QuickCheck 的素数生成器的一种方法(从 http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell 中窃取 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)在您的属性(property)中。