MA522 Homework 1 (due Wed Oct 3, 16h59, by email or in my mailbox in SAS 3151). Problem 1: Please consider the Repeated Squaring Algorithm 4.8 in Modern Computer Algebra. Modify the algorithm to radix 8 representation of the exponent n and using pre-computed powers a^3, a^5, a^7 obtained by 4 multiplications [see also E. C. Thurber, Duke Math. J., vol. 40, pp. 907-913 (1973)]. Then present an exponent n for which your modification saves at least 3 multiplications compared to Algorithm 4.8. Problem 2 is Problem 3.25 [on page 60 in von zur Gathen and Gerhard 1999, on page 63 in von zur Gathen and Gerhard 2003, on page 65 in von zur Gathen and Gerhard 2013]: We consider the following recursive algorithm for computing the gcd of two integers: Algorithm 3.17 Binary Euclidean Algorithm Input: a, b exist in N >0 Output: gcd(a,b) exist in N 1. If a = b then return a 2. If both a and b are even return 2 * gcd(a/2, b/2) 3. If exactly one of the two numbers, say a, is even then return gcd(a/2, b) 4. If both a and b are odd and, say, a > b, then return gcd((a - b)/2, b) (i) Run the algorithm on the examples of exercise 3.11 a. 34, 21 b. 136, 51 c. 481, 325 d. 8771, 3206 (ii) Prove that the algorithm works correctly (iii) Find a "good" upper bound on the recursion depth of the algorithm, and show that it takes O(n*n) word operations on inputs of length at most n (iv) Modify the algorithm so that it additionally computes s,t exist in N such that sa + tb = gcd(a,b) Problem 3: Richard Brent in 1980 gave a different algorithm than Floyd's for finding a cycle in a sequence x_0, x_1=f(x), x_2=f(f(x)),... that uses fewer applications of f and again only 2 function values stored for "equality testing." Describe Brent's approach, possibly giving a Maple procedure, by either searching the Internet/literature or expanding my hint. In particular, compare the number of function applications to Floyd's cycle finder. Hint: for all n there exists k such that n <= 2^k < 2n. One compares for all i the value x_{2^i} with all x_{2^i+1},x_{2^i+2},...,x_{2^{i+1}}. Optional: modify procedure cycle_indices in the posted Maple files pollard_rho.mpl to use Brent's idea, and then compare the performance on pollard_rho and discrete_log in pollard_rho.mws. ==========================================================================