Consider the $\text{fast square}$ and $\text{multiply algorithm}$ to calculate $x^y \text{ 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 \: \text{ 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 \text{ mod } N$;
end
5. $v = v^2 \text{ mod } N; \: z = \lfloor \frac{z}{2} \rfloor$
end
6. return $u$.
What is the time complexity of the algorithm 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(log^2 \: N)$, when the positive integers involved are less than $N$.]
