ISI2013-PCB-CS-1a,b

Question

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 \leq 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 $\equiv$ 1 mod 2 then 4. u = uv mod N;

end 5. $v = v^2 \: mod \: N; \: z = \lfloor \frac{z}{2} \rfloor$

end

6. return u

1. 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). 
2. Discuss whether your program works perfectly for all possible input combinations.