Labs Homeworks |
## HW3## HW3: Due Fri 9th Feb before 11:59:59pmQ1. (10 points) Is \(4^{1536} \equiv 9^{4824} \mod 35\)? Show all work to support your answer. Q2. (10 points) Solve \(x^{86} \equiv 6 \mod 29\), i.e., find the value \(x\) for which the equation is true. 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. ## Important:You must show all the detailed steps to get credit for a question. Submission must be in |

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