使用QuickCheck生成素数

Question

背景

为了好玩，我正在尝试编写一个 quick-check 属性，可以测试 使用 RSA 进行加密 的基本思想。

• 选择两个不同的质数 p 和 q。
• 令 N = p*q
• e 是与 (p-1)(q-1) 互质 的某个数字（实践中，e 通常取 3 以实现快速编码）。
• d 是对于模 (p-1)(q-1)，e 的 模反元素。

对于所有使得 1 < x < N 的 x，恒有 (x^e)^d = x 模 N

换句话说，x 是“消息”，将其提高到模 N 的 e 次方是“编码”消息的行为，而将已编码的消息提高到模 N 的 d 次方是“解码”它的行为。

（该属性对于 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和随机博客，提供模数乘法逆元的实现）

问题

问题显而易见：属性上有太多限制，使其无法使用。 尝试在ghci中调用quickCheck prop_rsa会让我的终端挂起。

所以我在QuickCheck手册中找了一些信息，它说：

属性可以采取以下形式

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

如何为质数创建一个<generator>？ 或者其他限制条件，这样quickCheck就不必筛选出大量失败的条件了吗？

欢迎任何其他一般建议（特别是关于QuickCheck）。

- Dan Burton

---

有趣的事实：QuickCheck 帮助我看到 q 和 p 必须是不同的。在我有这个要求之前，它能够找到 q == p 时失败的示例。 - Dan Burton

太棒了，这是一个非常好的问题。很少有人会花这么多心思来表达他们想知道的事情。点赞。 - Aurum Aquila

你可以使用Rabin-Miller概率测试；http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html - Paul Johnson

刚刚在这里发现了Rabin-Miller测试的实现：http://bonsaicode.wordpress.com/2009/05/01/programming-praxis-primality-checking/ - Paul Johnson

@Paul 非常好！我一直在调整测试，使其仅使用小质数，主要是因为测试大数的素性变得繁琐。我会看看如何将其融入我的代码中。 - Dan Burton

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)。

- jacobm

---

你可能想要使用库代码来生成质数，它应该会更快一些：http://hackage.haskell.org/package/primes - barsoap

@barsoap的代码可能比我或jacobm写的更好，但是isPrime函数的文档目前说：“对于最小质因数很大的数字，它是不切实际的。” 维基百科上有许多关于更快素性测试的有趣信息，我可以尝试一下。 - Dan Burton

这是一个很好的答案；我试过了，感觉还不错。但并不完全符合我的要求。我特别想在这里使用 forAll。受你的答案启发，我实际上已经想出了一些东西，但我想等待看看是否有其他人有什么深刻的见解，然后再发布它。 - Dan Burton

Answer 2

好的，这是我做的事情。

文件顶部

{-# LANGUAGE NoMonomorphismRestriction #-}

import Test.QuickCheck
import Control.Applicative

除了prop_rsa，所有代码均按照问题中的给定方式编写。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 的魔法是什么，但我相信这是正确的。我进行了一些临时调整，以确保在我搞砸条件时它会失败，并确保嵌套的 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为false时，它是未定义的。换句话说，在整数a和b互质时，a才有一个乘法逆元（mod b）。

- Dan Burton