Consider the fast square and multiply algorithm to calculate x y mod N as given below, where x, y, N are positive integers and 1 ≤ x, y < N.
Input: x, y, N
Output: x y mod N
1. z = y, u = 1, v = x;
2. while z > 0 do
3. if z ≡ 1 mod 2 then
4. u = uv mod N;
end if
5. v = v 2 mod N; z = ⌊ z 2 ⌋;
end while
6. return u
(a) Write a C function to implement the algorithm. Your function should take three arguments x, y and N, and return the value x y mod N, all of which are of type unsigned long long (i.e., 64-bit unsigned integers).
(b) Discuss whether your program works perfectly for all possible input combinations.
(c) What is the time complexity of the algorithm (not your C implementation) in terms of N? [Note that N can be a very large integer, e.g., more than 512 bits. Assume that the time complexity of modular multiplication is O(log2 N), when the positive integers involved are less than N.]
