通过生成素数来使用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是"消息",将其提升到e功率mod N是"编码"消息的行为,并且将编码消息提升到d功率mod 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中调用使我的终端挂起.

所以我在QuickCheck手册上略微探讨了一下,它说:

属性可以采取形式

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