Utilisez QuickCheck en générant des nombres premiers

Question

Arrière-plan

Pour m'amuser, j'essaie d'écrire une propriété pour une vérification rapide qui peut tester l'idée de base derrière cryptographie avec RSA.

• Choisissez deux nombres premiers distincts, p et q.
• Laisser N = p*q
• e est un nombre relativement premier à (p-1)(q-1) (en pratique, e vaut généralement 3 pour un encodage rapide)
• d est le inverse modulaire de e module (p-1)(q-1)

Pour tous x tel que 1 < x < N, c'est toujours vrai que (x^e)^d = x modulo N

Autrement dit, x est le "message", l'élevant au ele mod de puissance N est l'acte de "coder" le message et d'élever le message codé vers le dle mod de puissance N est l'acte de le « décoder ».

(La propriété est aussi trivialement vraie pour x = 1, un cas qui est son propre cryptage)

Code

Voici les méthodes que j'ai codées jusqu'à présent :

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

(Merci, Google et Random Blog, pour le implémentation de l'inverse multiplicatif modulaire)

Question

Le problème devrait être évident :il y a beaucoup trop de conditions sur la propriété pour la rendre utilisable.Essayer d'invoquer quickCheck prop_rsa dans ghci, mon terminal s'est bloqué.

J'ai donc fouillé le Manuel QuickCheck un peu, et il dit :

Les propriétés peuvent prendre la forme

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

Comment puis-je faire un <generator> pour les nombres premiers ?Ou avec les autres contraintes, pour que quickCheck n'est-il pas nécessaire de passer au crible un tas de conditions qui ont échoué ?

Tout autre conseil général (notamment concernant QuickCheck) est le bienvenu.

Answer 1

OK alors voici ce que j'ai fait.

Haut du dossier

{-# LANGUAGE NoMonomorphismRestriction #-}

import Test.QuickCheck
import Control.Applicative

Tout le code indiqué dans la question, à l'exception de prop_rsa.Cela a été (évidemment) fortement modifié :

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

Le type pour primePair est Gen (Int, Int), et le type pour genUnder est Int -> Gen Int.Je ne suis pas exactement sûr de ce qui se cache derrière la magie forAll mais je suis presque sûr que c'est correct.J'ai fait quelques ajustements ad hoc pour 1) m'assurer qu'il échoue si je gâche les conditions et 2) m'assurer que l'imbriqué forAll fait varier la valeur de x à travers les cas de test.

Voici donc comment écrire ces générateurs.Une fois que j'ai réalisé que <generator> dans la documentation signifiait juste quelque chose de type Gen a, c'était du gâteau.

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 il m'a fallu quelques essais et erreurs pour réussir ;Je savais que certains combinateurs aiment ça devrait travail, mais je ne suis toujours pas aussi familier avec fmap, <$> et <*> comme j'aimerais être.J'ai limité le calcul à une sélection uniquement parmi les 2 500 premiers nombres premiers ;sinon, il voulait apparemment en choisir de très gros qui prenaient une éternité à générer.

Chose aléatoire à noter

Grâce à la paresse, d = mInverse e t n’est calculé que si les conditions sont remplies.Ce qui est bien, car on ne sait pas quand la condition rPrime e t c'est faux.En anglais, un entier a n'a d'inverse multiplicatif (mod b) que lorsque a et b sont relativement premiers.

Answer 2

Voici une façon de créer un générateur de nombres premiers compatible avec QuickCheck (en volant une implémentation de Sieve of Eratosthenes à 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)

Il peut être utilisé dans QuickCheck comme suit :

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

Pour votre usage, vous remplaceriez p et q avec (Prime p) et (Prime q) dans votre propriété.