# Homework 5CSE/MATH 467Due: 23 September, 20161. (Coding problem from last week) Write fast exponenti

Homework 5CSE/MATH 467Due: 23 September, 20161. (Coding problem from last week) Write fast exponentiation code and findten 10-digit probable primes (with respect to base 2).132. a) Determine 1313 .13b) Determine 1313 .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 ? ZAlgorithm: Define recursively Ak (kth interpolation) and wk (kth weight) bythe 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 . . . mr?1 satisfiesthe system of congruencesx ? a1…x ? armod m1mod mrB. At most how many multiplications modulo mk are actually involved in thekth step if we take care to keep the sizes of numbers down? (Ignore thosecoming from multiprecision considerations and from the Knuth algorithm tocompute multiplicative inverses modulo mk .)4. Let p and q be odd primes with difference ? = p ? q > 0 and productn = pq.?(a) Show that the Fermat factorization method involves (p + q)/2 ? d neincreases in x to find x and y such that n = x2 ? y 2 .(b) Show thatp+q ?p+q ?1? pq+ pq = ? 2 .224(c) Assume that ? is so much smaller than p that we can consider (p+q)/2 ??p and pq ? p. Show that then?2p+q ?? pq ? .28p2(d) Suppose that p and q are 100-digit primes (so that p, q ? 1099 ) andp ? q ? 1080 so the most significant 19 or 20 digits are the same. Showthat 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 Fermatmethod 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 maytake r = 2 as the base case.