Thread: Test whether the integer is a prime

1. Originally Posted by evinda
How do we see that $q$ must divide $ord_r{(n)}$ ?
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?

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$ ?

3. Originally Posted by evinda
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$ ?

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?

Originally Posted by I like Serena
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?
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?

5. Originally Posted by evinda
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?
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?
And in one of the iterations we could have $r-1$.

From :
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.

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

Originally Posted by I like Serena
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?
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}$.

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

7. 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.