Originally Posted by

**evinda**
But then we could also need to calculate $n^5 \mod{r}$, which is equal to $n^4 \cdot n \mod{r}$.

So why can we pick $n^2$ as an upper bound?

In the modular_pow algorithm we calculate base := (base * base) mod modulus

, where $0 \le \text{base} \le \text{modulus} -1$ each time.

And we calculate result:= (result * base) mod modulus

, where $0 \le \text{result, base} \le \text{modulus} -1$.

So at every step the biggest product we might calculate is $(\text{modulus} -1)(\text{modulus} -1)$, after which we reduce the result to be below $\text{modulus}$.

Suppose we have $r=17, n=19, i=10$.

Then the algorithm is:

\begin{array}{cccl}

base & exponent & result & code\\

19 & 10 & 1 & base := base \bmod 17\\

2 & 10 & 1 & base := (base * base) \bmod 17 ; exponent := exponent >> 1 \\

4 & 5 & 1 & result := (result * base) \bmod 17 ; exponent := exponent - 1 \\

4 & 4 & 4 & result := (base * base) \bmod 17 ; exponent := exponent >> 1 \\

16 & 2 & 4 & result := (base * base) \bmod 17 ; exponent := exponent >> 1 \\

1 & 1 & 4 & (result * base) \bmod 17 ; exponent := exponent - 1 \\

1 & 0 & 4

\end{array}

See how both result and base are always below $ r=17 < n=19$ (after the first step)?

And how the base can be 16, which gets multiplied with itself?

So $n^2$ is an upper bound.