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$ |
2. while z > 0 do |
3. if z $\equiv$ 1 mod 2 then |
4. u = uv mod N; |
5. $v = v^2 \: mod \: N; \: z = \lfloor \frac{z}{2} \rfloor$ |
end |
6. return u |
- 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).
- Discuss whether your program works perfectly for all possible input combinations.