5 CSE/MATH 467 Due: 23 September, 2016 1. (Coding problem from last week) Write fast exponentiation code and find ten 10-digit probable primes (with respect to base 2). 13 2. a) Determine 1313 %10. 13 b) Determine 1313 %15. 3. Recall that we formulated Garner's fast recursive general Chinese Remainder Theorem in the following way: Input: Moduli m1 , . . . , mr with gcd(mi , mj ) = 1 when i < j. Representatives a1 , . . . , ar Z Algorithm: Define recursively Ak (kth interpolation) and wk (kth weight) by the following: Intialization: w1 : = 0. w1 : = A1 : = a1 %m1 . Recursion: wk+1 : = (ak+1 Ak )(m1 mk ) %mk+1 Ak+1 : = Ak + (wk+1 m1 mk ), where (m1 mk )(m1 mk ) 1 mod mk+1 . A. Show by induction on r that Ar = w1 +w2 m1 + +wr m1 . . . mr1 satisfies the system of congruences x a1 .. . x ar mod m1 mod mr B. At most how many multiplications modulo mk are actually involved in the kth step if we take care to keep the sizes of numbers down? (Ignore those coming from multiprecision considerations and from the Knuth algorithm to compute multiplicative inverses modulo mk .) 4. Let p and q be odd primes with difference = p q > 0 and product n = pq. (a) Show that the Fermat factorization method involves (p + q)/2 d ne increases in x to find x and y such that n = x2 y 2 . (b) Show that \u0012 \u0013\u0012 \u0013 p+q p+q 1 pq + pq = 2 . 2 2 4 (c) Assume that is so much smaller than p that we can consider (p+q)/2 p and pq p. Show that then \u0013 \u0012 2 p+q pq . 2 8p 2 (d) Suppose that p and q are 100-digit primes (so that p, q 1099 ) and p q 1080 so the most significant 19 or 20 digits are the same. Show that the Fermat algorithm takes approximately 1060 increases in x. (e) If p and q are 100-digit primes with p q 1050 , show that the Fermat method finds the factorization with very few increases in x. 5. We showed in class that if m, n N are relatively prime, then (mn) = (m)(n). Prove by careful induction that if m1 , . . . , mr are pair-wise relatively prime positive integers, then (m1 mr ) = (m1 ) (mr ). You may take r = 2 as the base case