Use QuickCheck by generating primes

Question

Background

For fun, I'm trying to write a property for quick-check that can test the basic idea behind cryptography with RSA.

Choose two distinct primes, p and q.
Let N = p*q
e is some number relatively prime to (p-1)(q-1) (in practice, e is usually 3 for fast encoding)
d is the modular inverse of e modulo (p-1)(q-1)

For all x such that 1 < x < N, it is always true that (x^e)^d = x modulo N

In other words, x is the "message", raising it to the eth power mod N is the act of "encoding" the message, and raising the encoded message to the dth power mod N is the act of "decoding" it.

(The property is also trivially true for x = 1, a case which is its own encryption)

Code

Here are the methods I have coded up so far:

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

(Thanks, google and random blog, for the implementation of modular multiplicative inverse)

Question

The problem should be obvious: there are way too many conditions on the property to make it at all usable. Trying to invoke quickCheck prop_rsa in ghci made my terminal hang.

So I've poked around the QuickCheck manual a bit, and it says:

Properties may take the form

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

How do I make a <generator> for prime numbers? Or with the other constraints, so that quickCheck doesn't have to sift through a bunch of failed conditions?

Any other general advice (especially regarding QuickCheck) is welcome.

Fun fact: QuickCheck helped me see that q and p must be distinct. Before I had that requirement, it was able to find examples that failed the prop when q == p — Dan Burton
Props man, this is a beautifully asked question. Few people put this much effort into communicating what they want to know. Upvote. — Aurum Aquila
You could use the Rabin-Miller probabilistic test; mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html — Paul Johnson
Just found an implementation of the Rabin-Miller test here: bonsaicode.wordpress.com/2009/05/01/… — Paul Johnson
@Paul very nice! I've been working on tweaking the test so that it only uses small primes, mainly because testing larger numbers for primality was getting cumbersome. I'll take a look at working that into my code instead. — Dan Burton

jacobm jacobm · Accepted Answer · 2011-02-20T06:30:02

Here's one way to make a QuickCheck-compatible prime-number generator (stealing a Sieve of Eratosthenes implementation from 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)

It can be used in QuickCheck like so:

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

For your use, you'd replace p and q with (Prime p) and (Prime q) in your property.

Use QuickCheck by generating primes

2 Answers