Используйте QuickCheck для генерации простых чисел
Предпосылки
Ради интереса, я пытаюсь написать свойство для быстрой проверки, которая может проверить основную идею криптографии с RSA .
- Выберите два различных простых числа,
pиq. - Пусть
N = p * q e- некоторое число , относительное простое к(p-1) (q-1)(на практике , e обычно равно 3 для быстрого кодирования)d- это модульное обратноеeпо модулю(p-1) (q-1)
Для всех x таких, что 1 (x ^ e) ^ d = x по модулю 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 и случайный блог, за реализацию модульного мультипликативного обратного )
Вопрос
Проблема должна быть очевидной: слишком много условий на свойство, чтобы его можно было вообще использовать. .Попытка вызвать quickCheck prop_rsa в ghci привела к зависанию моего терминала.
Итак, я немного покопался в руководстве QuickCheck , и там сказано:
Свойства могут принимать форму
forAll$ \ ->
Как создать для простых чисел? Или с другими ограничениями, так что quickCheck не нужно просеивать кучу неудачных условий?
Любые другие общие советы (особенно относительно QuickCheck) приветствуются.