Q1. (10 points) Is \(4^{1536} \equiv 9^{4824} \mod 35\)? Show all work to support your answer. **Hint**: 35 is not a prime so you cannot apply Fermat's little theorem directly. However, 35 is a product of primes and you can apply the theorem to those prime factors. You can also use modular exponentiation approach (but show all steps).

Q2. (10 points) Solve \(x^{86} \equiv 6 \mod 29\), i.e., find the value \(x\) for which the equation is true. **Hint**: You can use fermat's little theorem.

Q3. (10 points) Prove that \(gcd(F_{n+1}, F_n) = 1\), for \(n \ge 1\), where \(F_n\) is the n-th Fibonacci element.

Q4. (10 points) Assume that the cost to multiply a n-bit integer with a m-bit integer is O(nm). Given integers x and y with n-bits and m-bits, respectively, give an efficient algorithm to compute \(x^y\). Show that the method is correct, and analyze its running time.

You must show all the detailed steps to get credit for a question.

Submission must be in **PDF** format only.

Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/HW3

Page last modified on February 05, 2018, at 02:15 PM