FSA Lab Exercises, Final Set Jan van Eijck CWI & ILLC, Amsterdam October, 2014 module FSAlab5 where import Data.List import System.Random We need System.Random because we are going to explore a probabilistic algorithm for efficient primality checking. Public key cryptography is based on the assumption that factorization of large numbers (products of large primes) is hard, while finding and multiplying large primes is easy. With large numbers, no efficient integer factorization algorithm is known (unless we work with quantum computers). See http://en.wikipedia.org/ wiki/Integer_factorization for background. Here is a naive algorithm for factorization: factors :: Integer -> [Integer] factors n = factors’ n 2 where factors’ 1 _ = [] factors’ n m | n ‘mod‘ m == 0 = m : factors’ (n ‘div‘ m) m | otherwise = factors’ n (m+1) This can be improved somewhat by the observation that if all m with 2 ≤ m < n do not divide n, and m2 > n, then m and n are relatively prime. This gives: factors :: Integer -> [Integer] factors n = factors’ n 2 where factors’ 1 _ = [] factors’ n m | n ‘mod‘ m == 0 = m : factors’ (n ‘div‘ m) m | mˆ2 > n = [n] | otherwise = factors’ n (m+1) Exercise 1 Can you improve this further, using the fact that we are looking for factors that are prime, and that instead of trying (m + 1) it is enough to try out the next prime number? In a sensational paper PRIMES is in P Agrawal et al. [2004] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena presented a deterministic efficient algorithm for testing primality. See http://en.wikipedia.org/wiki/AKS_primality_ test. Previously known efficient algorithms were probabilistic. These exercises explore modular arithmetic on the integers, ending with primality testing using probabilistic algorithms, and the use of the fact that factorization is hard while primality testing is easy for public key cryptography. We start with modular arithmetic, using the built in function rem from Haskell. A key ingredient of efficient testing for primality is efficient exponentiation modulo a prime number. Modular addition: addM :: Integer -> Integer -> Integer -> Integer addM x y = rem (x+y) Modular multiplication: multM :: Integer -> Integer -> Integer -> Integer multM x y = rem (x*y) Modular exponentiation: expM :: Integer -> Integer -> Integer -> Integer expM x y = rem (xˆy) This is not efficient, for we first compute xy , and then reduce the result modulo N . Instead, we should have performed the intermediate computation steps for xy modulo N . Exercise 2 Implement a function exM :: Integer -> Integer -> Integer -> Integer that does modular exponentiation of xy in polynomial time, by repeatedly squaring modulo N . E.g., x33 mod 5 can be computed by means of x33 (mod 5) = x32 (mod 5) × x (mod 5). x32 (mod N ) is computed in five steps by means of repeatedly squaring modulo N: x (mod N ) → x2 (mod N ) → x4 (mod N ) → . . . → x32 (mod N ). If this explanation is too concise, look up relevant literature. Exercise 3 Check that your implementation is more efficient than expM by running a number of relevant tests and documenting the results. Primality testing using a probabilistic algorithm is based on efficient exponentiation modulo. This uses Fermat’s Little Theorem, which states the following. Theorem 4 (Fermat) If p is prime, then for every 1 ≤ a < p: ap−1 ≡ 1 (mod p). To see what this says, first look at some examples: Assume p = 5. Let us check 24 , 34 and 54 . 24 = 16 ≡ 1 (mod 5), 34 = 81 ≡ 1 (mod 5), 44 = 256 ≡ 1 (mod 5). It turns out that for every 1 ≤ a < p, the set of remainders modulo p is equal to their product with a modulo p. In other words, multiplying the set {1, . . . , p − 1} with a modulo p is simply to permute the set. You should try this out for p = 5 and a = 3, and you will find that {1, 2, 3, 4} = {3×1 (mod 5), 3×2 (mod 5), 3×3 (mod 5), 3×4 (mod 5)}. Multiplying the numbers in the sets, we get 4! ≡ 34 × 4! (mod 5). Dividing both sides by 4!, this gives 34 ≡ 1 (mod 5). Now for the general case. We have to show that if the numbers in the set S = {1, . . . , p − 1} get multiplied by a modulo p, the resulting numbers are distinct and 6= 0. So let i 6= j ∈ S, and consider ai and aj. Suppose ai ≡ aj (mod p). Then i ≡ j (mod p) and contradiction with i 6= j. So ai and aj are distinct modulo p. If ai ≡ 0 then, since a and p are relatively prime, we can divide by a and get i ≡ 0, and contradiction. So the resulting numbers are 6= 0. This means the result of multiplying the numbers in S with a modulo p is a permutation of S. This gives S = {1, . . . , p − 1} = {a × 1 mod p, . . . , a × p − 1 mod p}. Multiplying the numbers left and right gives: (p − 1)! = ap−1 × (p − 1)! (mod p). We can divide both sides by (p − 1)! because (p − 1)! and p are relatively prime. This gives ap−1 ≡ 1 (mod p). Fermat’s Test for Primality Fermat’s Test 1. Pick a with 1 < a < N at random. 2. Compute aN −1 (mod N ) using fast exponentiation. 3. If the outcome is 1, output ”Prime”, otherwise output ”Composite”. Problem with this: if N is indeed prime then aN −1 ≡ 1 (mod N ), and the test works fine. If N is composite, it may still happen that aN −1 ≡ 1 (mod N ), for Fermat’s Little Theorem does not specify what happens for composite numbers . . . In any case, here is an implementation, using fast exponentiation (your function exM): prime_test :: Integer -> IO Bool prime_test n = do a <- randomRIO (1, n-1) :: IO Integer return (exM a (n-1) n == 1) We can improve this by performing a sequence of k tests: prime :: Int -> Integer -> IO Bool prime k n = do as <- sequence $ fmap (\_-> randomRIO (1,n-1)) [1..k] return (all (\ a -> exM a (n-1) n == 1) as) Unfortunately, there are numbers that fool this test, so called Carmichael numbers. Exercise 5 Implement the algorithm of Rabin and Miller Miller [1976], Rabin [1980], which gives a version of probabilistic primality testing that cannot by fooled by Carmichael numbers. See http://en.wikipedia.org/wiki/Miller%E2% 80%93Rabin_primality_test. Exercise 6 Use the above to implement a trapdoor function: a bijection f : Zp → Zp for a large prime p that is efficient to compute, but for which f −1 is hard to compute. See http://en.wikipedia.org/wiki/Trapdoor_function and Diffie and Hellman [1976]. References M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004. W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. G. L. Miller. Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences, 13(3):300–317, 1976. M. O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1):128–138, 1980.

© Copyright 2018 ExploreDoc