FSA Lab Exercises, Final Set

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.

Download Report