MHB Test whether the integer is a prime

[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)