Test whether the integer is a prime

[evinda]

Then we check how many times the while-loop is executed. There is the following lemma.

View attachment 7628

First of all, how do we get that $\Omega\left(\frac{x}{\log{x}}\right)=\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

I got that $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}$... But is this in $\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

Also how do we get that $n^{\frac{x^{\frac{2}{3}}}{3}} <\Pi<n^{x^{\frac{2}{3}}}$ ? (Thinking)

 

[I like Serena]

Then we check how many times the while-loop is executed. There is the following lemma.

First of all, how do we get that $\Omega\left(\frac{x}{\log{x}}\right)=\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

I got that $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}$... But is this in $\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

Don't we have $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}
\ge \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}$ for sufficiently large $n$? (Wondering)

Also how do we get that $n^{\frac{x^{\frac{2}{3}}}{3}} <\Pi<n^{x^{\frac{2}{3}}}$ ? (Thinking)

Let $X=\lfloor x^{1/3}\rfloor$.
Then:
$$\mathit\Pi = \prod_{i=1}^X (n^i-1) < \prod_{i=1}^X n^X = n^{X^2}$$
and:
$$\mathit\Pi = \prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1} = n^{\sum (i-1)} = n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$$
Isn't it? (Wondering)

 

[evinda]

Don't we have $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}
\ge \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}$ for sufficiently large $n$? (Wondering)

This holds when $\lceil \log{n}\rceil \geq \frac{(\log{\log{n}})^3}{8}$, right? If so, how can we easily prove this? Do we use induction?

Then we have the following.

$$\frac{x}{\log{x}} \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\log{n}+1)}} (\star)$$

We have that $4 \log{(\log{n}+1)} \leq 4 \log{(2 \log{n})}=4(\log{2}+\log{(\log{n})})=4(1+\log{(\log{n})}) \leq 4(2 \log{(\log{n})})=8 \log{(\log{n})}$.

So we get that $(\star) \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3 }{8 \log{(\log{n})}}=\lceil \log{n}\rceil^3 (\log{\log{n}})^2$.

Right? Or have I done something wrong? (Thinking)

Let $X=\lfloor x^{1/3}\rfloor$.
Then:
$$\mathit\Pi = \prod_{i=1}^X (n^i-1) < \prod_{i=1}^X n^X = n^{X^2}$$

I see... (Nod)

$$\mathit\Pi = \prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1} = n^{\sum (i-1)} = n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$$
Isn't it? (Wondering)

Why does it hold that $\prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1}$ ?

The last inequality holds for $X>3$, right?

 

[I like Serena]

This holds when $\lceil \log{n}\rceil \geq \frac{(\log{\log{n}})^3}{8}$, right? If so, how can we easily prove this? Do we use induction?

Can't we use that $\log n > \log\log n > \log\log\log n > 8$ for sufficiently large $n$? (Wondering)

Then we have the following.

$$\frac{x}{\log{x}} \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\log{n}+1)}} (\star)$$

We have that $4 \log{(\log{n}+1)} \leq 4 \log{(2 \log{n})}=4(\log{2}+\log{(\log{n})})=4(1+\log{(\log{n})}) \leq 4(2 \log{(\log{n})})=8 \log{(\log{n})}$.

So we get that $(\star) \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3 }{8 \log{(\log{n})}}=\lceil \log{n}\rceil^3 (\log{\log{n}})^2$.

Right? Or have I done something wrong?

All correct. (Nod)

Why does it hold that $\prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1}$ ?

The last inequality holds for $X>3$, right?

Doesn't it hold for any $X$ as long as $n \ge 2$?
That is:
$$n^i -1 = n^{i-1}(n-n^{-(i-1)})>n^{i-1}$$
(Thinking)

 

[evinda]

Can't we use that $\log n > \log\log n > \log\log\log n > 8$ for sufficiently large $n$? (Wondering)

So is it as follows?

$$\log{8}+3 \log{(\lceil \log{n}\rceil)}+3 \log{(\log{\log{n}})} \leq \log{(\log{n})}+3 \log{(\log{n}+1)}+3 \log{(\log{n})} \leq 4 \log{(\log{n})}+3 \log{(2 \log{n})}=7\log{(\log{n})}+3 \log{2}\leq 7 \log{(\log{n})}+3 \log{(\log{n})}=10 \log{\log{n}}$$

Thus, we have $\frac{x}{\log{x}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{10 \log{\log{n}}}=\frac{8}{10} \lceil \log{n}\rceil^3 (\log{\log{n}})^2= \Omega(\lceil \log{n}\rceil^3 (\log{\log{n}})^2)$.

Right?

Doesn't it hold for any $X$ as long as $n \ge 2$?
That is:
$$n^i -1 = n^{i-1}(n-n^{-(i-1)})>n^{i-1}$$
(Thinking)

This holds only when $n-n^{-(i-1)}>1 \Rightarrow n^i-n^{i-1}-1>0$, right? (Thinking)

 

[I like Serena]

So is it as follows?

$$\log{8}+3 \log{(\lceil \log{n}\rceil)}+3 \log{(\log{\log{n}})} \leq \log{(\log{n})}+3 \log{(\log{n}+1)}+3 \log{(\log{n})} \leq 4 \log{(\log{n})}+3 \log{(2 \log{n})}=7\log{(\log{n})}+3 \log{2}\leq 7 \log{(\log{n})}+3 \log{(\log{n})}=10 \log{\log{n}}$$

Thus, we have $\frac{x}{\log{x}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{10 \log{\log{n}}}=\frac{8}{10} \lceil \log{n}\rceil^3 (\log{\log{n}})^2= \Omega(\lceil \log{n}\rceil^3 (\log{\log{n}})^2)$.

Right?

Yep. (Nod)

This holds only when $n-n^{-(i-1)}>1 \Rightarrow n^i-n^{i-1}-1>0$, right?

Yes.
And $-(i-1)\le 0$, so with $n\ge 2$ we have that $n^{-(i-1)} \le 1$. (Thinking)

 

[evinda]

Yes.
And $-(i-1)\le 0$, so with $n\ge 2$ we have that $n^{-(i-1)} \le 1$. (Thinking)

So we have that $n^i-1>n^{i-1}$ only if $n-n^{-(i-1)}>1$.

And taking into consideration that $n \geq 2$ and $-(i-1) \leq 0$, we get that $n^{-(i-1)} \leq 1 \Rightarrow -n^{-(i-1)}\geq -1 \Rightarrow n-n^{-(i-1)} \geq n-1>1$, right?Do you maybe have an idea how we get that $k=O\left( \frac{\log{(\Pi)}}{\log{\log{(\Pi)}}}\right)$ ?

 

[I like Serena]

So we have that $n^i-1>n^{i-1}$ only if $n-n^{-(i-1)}>1$.

And taking into consideration that $n \geq 2$ and $-(i-1) \leq 0$, we get that $n^{-(i-1)} \leq 1 \Rightarrow -n^{-(i-1)}\geq -1 \Rightarrow n-n^{-(i-1)} \geq n-1>1$, right?

Just nitpicking, but shouldn't that last inequality be $\geq n-1\ge 1$? (Wondering)

Do you maybe have an idea how we get that $k=O\left( \frac{\log{(\Pi)}}{\log{\log{(\Pi)}}}\right)$ ?

What is the argument following lemma 3.6.8? (Wondering)

 

[evinda]

Just nitpicking, but shouldn't that last inequality be $\geq n-1\ge 1$? (Wondering)

Yes, right...

$$\mathit\Pi = \prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1} = n^{\sum (i-1)} = n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$$

Doesn't $n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$ only hold when $\frac{1}{2}X^2-\frac{1}{2}X>\frac{1}{3}X^2 \Rightarrow X>3$ ?

Also having shown that $\mathit\Pi > n^{\frac{1}{3}X^2}=n^{\frac{1}{3} \lfloor x^{\frac{1}{3}}\rfloor^2}$ we haven't shown yet that $\mathit\Pi > n^{\frac{1}{3}x^{\frac{2}{3}}}$, do we?

What is the argument following lemma 3.6.8? (Wondering)

View attachment 7630

For $x>1$, with $\pi(x)$ we denote the number of primes $p \leq x$.

 

[I like Serena]

Doesn't $n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$ only hold when $\frac{1}{2}X^2-\frac{1}{2}X>\frac{1}{3}X^2 \Rightarrow X>3$ ?

Also having shown that $\mathit\Pi > n^{\frac{1}{3}X^2}=n^{\frac{1}{3} \lfloor x^{\frac{1}{3}}\rfloor^2}$ we haven't shown yet that $\mathit\Pi > n^{\frac{1}{3}x^{\frac{2}{3}}}$, do we?

Indeed. (Thinking)

For $x>1$, with $\pi(x)$ we denote the number of primes $p \leq x$.

That leads up to $\mathit\Pi > (2k/e)^k$.
Taking logs brings us basically to $k\log k <c\cdot N$, where $N=\log\mathit\Pi$ and $c$ is some constant.
From there we are supposed to get to $k<c\cdot \frac{N}{\log N}=c\cdot \frac{\log\mathit\Pi}{\log\log\mathit\Pi}$.
It seems that is explained right after your fragment with 'an indirect argument'.
What comes after? (Thinking)

 

[evinda]

Indeed. (Thinking)

How else could we get the lower bound? (Thinking)

That leads up to $\mathit\Pi > (2k/e)^k$.
Taking logs brings us basically to $k\log k <c\cdot N$, where $N=\log\mathit\Pi$ and $c$ is some constant.
From there we are supposed to get to $k<c\cdot \frac{N}{\log N}=c\cdot \frac{\log\mathit\Pi}{\log\log\mathit\Pi}$.
It seems that is explained right after your fragment with 'an indirect argument'.
What comes after? (Thinking)

View attachment 7631

 

[I like Serena]

Also having shown that $\mathit\Pi > n^{\frac{1}{3}X^2}=n^{\frac{1}{3} \lfloor x^{\frac{1}{3}}\rfloor^2}$ we haven't shown yet that $\mathit\Pi > n^{\frac{1}{3}x^{\frac{2}{3}}}$, do we?

How else could we get the lower bound?

We have to tweak it a little.
Something like:
$$
\mathit\Pi > n^{\frac{1}{2}X(X-1)}>n^{\frac{1}{2}(X-1)^2}
=n^{\frac{1}{2}(\lfloor x^{1/3}\rfloor-1)^2}
>n^{\frac{1}{2}(x^{1/3}-2)^2}
>n^{\frac{1}{3}x^{2/3}}
$$
for sufficiently large $x$. (Thinking)

Do you maybe have an idea how we get that $k=O\left( \frac{\log{(\Pi)}}{\log{\log{(\Pi)}}}\right)$ ?

And indeed, the argument is a long one, but it seems to be all there, doesn't it? (Wondering)

 

[evinda]

We have to tweak it a little.
Something like:
$$
\mathit\Pi > n^{\frac{1}{2}X(X-1)}>n^{\frac{1}{2}(X-1)^2}
=n^{\frac{1}{2}(\lfloor x^{1/3}\rfloor-1)^2}
>n^{\frac{1}{2}(x^{1/3}-2)^2}
>n^{\frac{1}{3}x^{2/3}}
$$
for sufficiently large $x$. (Thinking)

The last inequality holds when $\frac{1}{2}(x^{\frac{1}{3}}-2)^2>\frac{1}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-4x^{\frac{1}{3}}+4>\frac{2}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-12x^{\frac{1}{3}}+12 > 0$.

So does $x$ have to be such that $x^{\frac{1}{3}}>\frac{12+ \sqrt{3 \cdot 2^5}}{2}$? (Thinking)

And indeed, the argument is a long one, but it seems to be all there, doesn't it? (Wondering)

But in our case we don't have that $k=\pi(\mathit\Pi )$, do we? (Thinking)

 

[I like Serena]

The last inequality holds when $\frac{1}{2}(x^{\frac{1}{3}}-2)^2>\frac{1}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-4x^{\frac{1}{3}}+4>\frac{2}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-12x^{\frac{1}{3}}+12 > 0$.

So does $x$ have to be such that $x^{\frac{1}{3}}>\frac{12+ \sqrt{3 \cdot 2^5}}{2}$? (Thinking)

Yep.

But in our case we don't have that $k=\pi(\mathit\Pi )$, do we? (Thinking)

Indeed. That's why the argument is similar. (Thinking)

 

[evinda]

Indeed. That's why the argument is similar. (Thinking)

Don't we have that $k \leq \pi(\mathit \Pi)$ and so $k=O{\left( \frac{\mathit \Pi}{\log{ \mathit \Pi}}\right)}$ ? Or am I wrong? (Thinking)

 

[evinda]

Taking logs brings us basically to $k\log k <c\cdot N$, where $N=\log\mathit\Pi$ and $c$ is some constant.
From there we are supposed to get to $k<c\cdot \frac{N}{\log N}=c\cdot \frac{\log\mathit\Pi}{\log\log\mathit\Pi}$.
(Thinking)

It seems that $O\left(\frac{\log{N}}{\log{\log{N}}}\right)$ is a known upper bound for the number of distince prime divisors of $N$, but I haven't understood how we can show this... (Thinking)

 

[I like Serena]

Isn't the first step where it says in the proof in http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103344.html#post103344 that $\mathit\Pi > 2^k\cdot k! > (2k/e)^k$ by lemma 3.6.8? (Wondering)

Yes. Do we use this somehow to conclude that $k=O{\left( \frac{\log{\mathit\Pi}}{\log{\log{\mathit\Pi}}}\right)}$ ? (Thinking)

Yes. Can't the next step be similar to what we have in post http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103372.html#post103372?
That is, we're taking logarithms,
$$\ln\mathit\Pi > k\cdot (\ln k + \ln 2 - 1)\tag{3.6.19a}$$
(Thinking)

So then we suppose that $k \geq \frac{\ln{\mathit\Pi}}{\ln{\ln{\mathit\Pi}}}$, in order to get a contradiction.

Using the relation $\ln{\mathit\Pi}>k(\ln{k}+\ln{2}-1)$ we get that

$$\ln{\mathit\Pi}> \frac{\ln{\mathit\Pi}}{\ln{\ln{\mathit\Pi}}}\left( \ln{\ln{\mathit\Pi}}-\ln{\ln{\ln{\Pi}}}+\ln{2}-1\right) \\ \Rightarrow \ln{\mathit\Pi} \ln{\ln{\mathit\Pi}}> \ln{\mathit\Pi} \ln{\ln{\mathit\Pi}}-\ln{\mathit\Pi} \ln{\ln{\ln{\mathit\Pi}}}+ \ln{2} \ln{\mathit\Pi}-\ln{\mathit\Pi} \\ \Rightarrow \ln{\mathit\Pi} (\ln{(\ln{\ln{\mathit\Pi}})}+1-\ln{2})>0$$

Do we now look at the function $f(x)= \ln{x}(\ln{\ln{\ln{x}}}+1-\ln{2})$ ?

If so, accrding to Wolfram, it has one solution and its derivate has no solution. What can we get from this? (Thinking)

Isn't that expression true for sufficiently large $x$? And the function positive as well?
Then it won't lead to a contradiction. (Worried)In the argument given in http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103374.html#post103374, we assumed that $k \ge \frac{2N}{\ln N}$. Note the extra factor $2$.

So let's first define $M=\ln\mathit\Pi$, and let's assume that $k\ge \frac{2M}{\ln M}$ for a contradiction.
Then we get:
$$M>k\cdot(\ln k + \ln 2 - 1) \tag{3.6.19a}$$
and it follows, when $\ln M > 0$, that:
$$M>\frac{2M}{\ln M}\cdot\left(\ln\left(\frac{2M}{\ln M}\right) + \ln 2 - 1\right) \\
\Rightarrow\quad\frac 12\ln M > \ln\left(\frac{2M}{\ln M}\right)+ \ln 2 - 1 \\
\Rightarrow\quad\frac 12\ln M > \ln M - \ln\ln M+ 2\ln 2 - 1 \\
\Rightarrow\quad(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1$$
so by obvious transformations,
$$(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1\tag{3.6.20a}$$

Now we can look at the function $f: x \mapsto (1-\frac 12)\ln x - \ln\ln x + 2\ln 2 - 1$, which is defined for $x > 1$, can't we? (Wondering)

 

[evinda]

In the argument given in http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103374.html#post103374, we assumed that $k \ge \frac{2N}{\ln N}$. Note the extra factor $2$.

So let's first define $M=\ln\mathit\Pi$, and let's assume that $k\ge \frac{2M}{\ln M}$ for a contradiction.
Then we get:
$$M>k\cdot(\ln k + \ln 2 - 1) \tag{3.6.19a}$$
and it follows, when $\ln M > 0$, that:
$$M>\frac{2M}{\ln M}\cdot\left(\ln\left(\frac{2M}{\ln M}\right) + \ln 2 - 1\right) \\
\Rightarrow\quad\frac 12\ln M > \ln\left(\frac{2M}{\ln M}\right)+ \ln 2 - 1 \\
\Rightarrow\quad\frac 12\ln M > \ln M - \ln\ln M+ 2\ln 2 - 1 \\
\Rightarrow\quad(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1$$
so by obvious transformations,
$$(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1\tag{3.6.20a}$$

Now we can look at the function $f: x \mapsto (1-\frac 12)\ln x - \ln\ln x + 2\ln 2 - 1$, which is defined for $x > 1$, can't we? (Wondering)

We have that $f(x)>0$ for $x>1$.

Then $f'(x)=\frac{\ln{x}-2}{2 x \ln{x}}$.

$f'(x)=0 \Rightarrow x=e^2$.

For $x> e^2$ we have that $f'(x)>0$ and so $f$ is increasing.

For $1<x<e^2$ we have that $f'(x)<0$ and so $f$ is decreasing.

So we get that for any $x>1$, $f(x)>f(e^2)=\ln{2} \Rightarrow \frac{1}{2} \ln{x}-\ln\ln x+ 2\ln 2-1>\ln{2}>0$, contradicting the relation $(3.6.20a)$.

Is everything right? (Thinking)

 

[I like Serena]

We have that $f(x)>0$ for $x>1$.

We don't have this yet. It's what we want to prove don't we? (Wondering)

Then $f'(x)=\frac{\ln{x}-2}{2 x \ln{x}}$.

$f'(x)=0 \Rightarrow x=e^2$.

For $x> e^2$ we have that $f'(x)>0$ and so $f$ is increasing.

For $1<x<e^2$ we have that $f'(x)<0$ and so $f$ is decreasing.

So we get that for any $x>1$, $f(x)>f(e^2)=\ln{2} \Rightarrow \frac{1}{2} \ln{x}-\ln\ln x+ 2\ln 2-1>\ln{2}>0$, contradicting the relation $(3.6.20a)$.

Yep. (Nod)

(Although shouldn't it be $f(x)\ge f(e^2)$?)

 

[evinda]

We don't have this yet. It's what we want to prove don't we? (Wondering)

Yes, right... (Nod)

Yep. (Nod)

(Although shouldn't it be $f(x)\ge f(e^2)$?)

Yes, I see... (Nod)

View attachment 7642

How do we see that $q$ must divide $ord_r{(n)}$ ? (Thinking)

 

[I like Serena]

How do we see that $q$ must divide $ord_r{(n)}$ ? (Thinking)

From what came before we have that:
$\operatorname{ord}_r n \mid r-1 = qm \tag 1$
$\operatorname{ord}_r n > x^{1/3} \ge m \tag 2$

Suppose that the prime $q\not\mid \operatorname{ord}_r n$.
Then by (1) it follows that $\operatorname{ord}_r n \mid m$, doesn't it?
Thus $\operatorname{ord}_r n \le m$, which is a contradiction with (2) isn't it? (Wondering)

 

[evinda]

I have also an other question. It says the following about the algorithm of post #17.View attachment 7781Why are the numbers bounded by $n^2$ and not by $n$ ? (Thinking)

 

[I like Serena]

I have also an other question. It says the following about the algorithm of post #17.

Why are the numbers bounded by $n^2$ and not by $n$ ? (Thinking)

View attachment 7583

In line 6 we're calculating $n^i\bmod r$ where $r$ can be as high as $n-1$.
With the fast exponentiation algorithm that means we need to evaluate numbers up to $(r-1)^2 = (n-2)^2$ don't we? (Wondering)

 

[evinda]

In line 6 we're calculating $n^i\bmod r$ where $r$ can be as high as $n-1$.
With the fast exponentiation algorithm that means we need to evaluate numbers up to $(r-1)^2 = (n-2)^2$ don't we? (Wondering)

In line 6, don't we compute at the beginning $n \mod{r}$, then at the second interation $(n \mod r) \cdot (n \mod{r})$, and so on? (Thinking)

 

[I like Serena]

In line 6, don't we compute at the beginning $n \mod{r}$, then at the second interation $(n \mod r) \cdot (n \mod{r})$, and so on? (Thinking)

Yes.
So the result of the first iteration is $n^2 \bmod r$.
Then we calculate $(n^2 \bmod r)\cdot (n^2 \bmod r)$ don't we? (Wondering)
And in one of the iterations we could have $r-1$.

From wiki:

The following is an example in pseudocode based on Applied Cryptography by Bruce Schneier.[1] The inputs base, exponent, and modulus correspond to b, e, and m in the equations given above.​

function modular_pow(base, exponent, modulus)
    if modulus = 1 then return 0
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

As you can see, we even have an assert in there that says we need to have support up to $(r-1)^2$. (Worried)

 

[evinda]

Yes.
So the result of the first iteration is $n^2 \bmod r$.
Then we calculate $(n^2 \bmod r)\cdot (n^2 \bmod r)$ don't we? (Wondering)
And in one of the iterations we could have $r-1$.

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

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

 

[I like Serena]

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

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

In the modular_pow algorithm we calculate [M]base := (base * base) mod modulus[/M], where $0 \le \text{base} \le \text{modulus} -1$ each time.
And we calculate [M]result:= (result * base) mod modulus[/M], 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. (Thinking)