Questions about proof about primality testing

[evinda]

Hello! (Wave)

I have read the proof that primality testing is in NP and I have a question about it.

The proof is the following:Note that the group $(\mathbb{Z}/ N \mathbb{Z})^{\ast}$ is of order $N-1$ iff $N$ is prime. And more over, it is a cyclic group of order $N-1$ iff $N$ is a prime. Thus, we shall find a witness or a certificate that the group is cyclic.
How do we show that a group is cyclic? We guess a generator $\alpha$. If we are able to show that $\alpha^n \neq 1$ for any $n<N-1$ we are done. Note that $\alpha^{N-1}=1$ anyway. Therefore, we just need to check that $\alpha^{\frac{N-1}{p_i}} \neq 1$ for every prime divisor $p_i$ of $N-1$.

Therefore, we not only guess the generator $\alpha$, we guess the factors $p_1, p_2, \dots, p_k$ of $N-1$. But how do we know that the guessed $p_i$s are indeed primes? We guess its witnesses too; induction. Aren't we going in circles? Actually no since the numbers $p_i$s are quite small and it still won't blow up the size of the final certificate.

Let us try and see how large the witness/certificate can get. How large can the prime factors of $N-1$ be? Since $N$ is a prime, $N-1$ is certainly composite (unless $N$ was 2 , a worthless case which can be handled right at the beginning). The largest factor of $N-1$ can be of size atmost $\sqrt{N}$. How many factors can there exist? Atmost $\log{(N-1)}$ of them. Thus if $N-1=p_1 p_2 \cdots p_k$ then our witness would be $(\alpha, p_1, p_2, \cdots, p_k)$ and the certificate of each of the $p_i$s. The input is of size $\log{N}$ and let $S(\ell)$ be the size of the witness for input of length $\ell$. Then:

$$S(\log{N})=\log^2N+S(\log{p_1})+S(\log{p_2})+ \dots+S(\log{p_k}) \\= \log^2 N+ (\log{p_1})^c+(\log{p_2})^c+ \dots+(\log{p_k})^c \\ \leq \log^2N+(\log{p_1}+ \dots+ \log{p_k})^c \\ = \log^2N+(\log{(N-1)})^c=O((\log{N})^c)$$

And since the witness is just polynomially bounded in the size of the input, we can guess the entire certificate and verify. Thus primality testing is in NP.First of all, do we suppose that $N$ is a prime and that's why we have that $a^{N-1}=1$ ?

At this part:

we guess the factors $p_1, p_2, \dots, p_k$ of $N-1$. But how do we know that the guessed $p_i$s are indeed primes? We guess its witnesses too; induction.

is it meant that we pick some $b_i \in \mathbb{Z}/p_i\mathbb{Z}, i \in \{1, \dots, k\}$ and want to verify that $b_i^{\frac{p_i-1}{q_j}} \neq 1, \forall j$, where with $q_j$ all the prime divisors of $p_i-1$ are meant?In addition, it holds that $S(\log{N})=\log^2N+S(\log{p_1})+S(\log{p_2})+ \dots+S(\log{p_k})$ . How do we get the $\log^2N$ at the sum?

And why does it hold that $S(\log{p_i})=(\log{p_i})^c $ ? (Thinking)

 

[I like Serena]

First of all, do we suppose that $N$ is a prime and that's why we have that $a^{N-1}=1$ ?

Hey evinda! (Smile)

It's the Little theorem of Fermat: $a^{p-1}\equiv 1 \pmod p$ if $p$ is prime and $a$ is coprime.

is it meant that we pick some $b_i \in \mathbb{Z}/p_i\mathbb{Z}, i \in \{1, \dots, k\}$ and want to verify that $b_i^{\frac{p_i-1}{q_j}} \neq 1, \forall j$, where with $q_j$ all the prime divisors of $p_i-1$ are meant?

Yes. We repeat the procedure for $N' = p_1$ and so on.

In addition, it holds that $S(\log{N})=\log^2N+S(\log{p_1})+S(\log{p_2})+ \dots+S(\log{p_k})$ . How do we get the $\log^2N$ at the sum?

And why does it hold that $S(\log{p_i})=(\log{p_i})^c $ ?

What is the definition of the size of a witness? (Wondering)

 

[evinda]

Hey evinda! (Smile)

It's the Little theorem of Fermat: $a^{p-1}\equiv 1 \pmod p$ if $p$ is prime and $a$ is coprime.

Ah, so we suppose that $N$ is a prime and we want to show that in this case $(\mathbb{Z}/ N\mathbb{Z})^{\ast}$ is cyclic, right?

Yes. We repeat the procedure for $N' = p_1$ and so on.

I see... (Nod)

What is the definition of the size of a witness? (Wondering)

It isn't given a definiton. But we have the following:NP is the class of languages $L$ such there exists a polynomial time verification scheme $A(x,y)$ such that $x \in L$ iff there exists a witness $y$ such that $|y|<|x|^c$ for some constant $c$ and $A(x,y)=1$.

 

[I like Serena]

Ah, so we suppose that $N$ is a prime and we want to show that in this case $(\mathbb{Z}/ N\mathbb{Z})^{\ast}$ is cyclic, right?

Yes.
If the equation does not hold for a coprime a, that is proof that N is composite.
And if it does hold, the result is inconclusive.

It isn't given a definiton. But we have the following:

NP is the class of languages $L$ such there exists a polynomial time verification scheme $A(x,y)$ such that $x \in L$ iff there exists a witness $y$ such that $|y|<|x|^c$ for some constant $c$ and $A(x,y)=1$.

I think we are looking at the induction step of a proof by induction.
That means that we assume that $S(p_i) = O(|p_i|^c)$ for $p_i < N$, and that we try to prove that $S(N) = O(|N|^c)$.

Now suppose we have a witness $(\alpha, p_1, ..., p_k)$, which has length $\ell = \log N$.
What would we actually have to do to verify if N is composite? (Wondering)

 

[evinda]

Yes.
If the equation does not hold for a coprime a, that is proof that N is composite.
And if it does hold, the result is inconclusive.

Why is the result inconclusive, if it does hold , although we have that $(\mathbb{Z}/N \mathbb{Z})^{\ast}$ is a cyclic group of order $N-1$ iff $N$ is a prime?

How do we show that a group is cyclic? We guess a generator $\alpha$. If we are able to show that $\alpha^n \neq 1$ for any $n<N-1$ we are done. Note that $\alpha^{N-1}=1$ anyway. Therefore, we just need to check that $\alpha^{\frac{N-1}{p_i}} \neq 1$ for every prime divisor $p_i$ of $N-1$.

Reading this again, I got confused... Why do we check if $\alpha^{\frac{N-1}{p_i}} \neq 1$ and not if $\alpha^{p_i} \neq 1$ ?

I think we are looking at the induction step of a proof by induction.
That means that we assume that $S(p_i) = O(|p_i|^c)$ for $p_i < N$, and that we try to prove that $S(N) = O(|N|^c)$.

A ok... But how do we get this formula for $S$? (Thinking)

Now suppose we have a witness $(\alpha, p_1, ..., p_k)$, which has length $\ell = \log N$.
What would we actually have to do to verify if N is composite? (Wondering)

We would check if $\alpha^{\frac{N-1}{p_1}}, \dots, \alpha^{\frac{N-1}{p_k}} \neq 1$.
If all these inequalities hold, don't we deduce that $N$ is a prime? (Thinking)

Given the witness $(\alpha, p_1, ..., p_k)$, we just need to make $k$ operations, namely to find the powers $\alpha^{\frac{N-1}{p_j}}, j=1, \dots, k$, don't we?

 

[I like Serena]

Why is the result inconclusive, if it does hold , although we have that $(\mathbb{Z}/N \mathbb{Z})^{\ast}$ is a cyclic group of order $N-1$ iff $N$ is a prime?

The 'iff' is misplaced in your statement. It should be 'if $N$ is a prime'.
Can we find an example of a cyclic group with $N$ composite?

The logical inversion of 'if A then B' is 'if not B then not A', isn't it?
What do we get if we apply that to 'if $N$ is prime then $(\mathbb{Z}/N \mathbb{Z})^{\ast}$ is cyclic'? (Wondering)

Reading this again, I got confused... Why do we check if $\alpha^{\frac{N-1}{p_i}} \neq 1$ and not if $\alpha^{p_i} \neq 1$ ?

We want to know if we can find an element $\alpha$ such that $\alpha^k \not\equiv 1 \pmod N$ for $k=1,..., N-2$.
Btw, such an element is called a primitive root. Do you perchance have any notes on that?

Anyway, instead of checking each and every $k$, we're trying to be smart about it.
We already know that $\alpha^{N-1}\equiv 1$.
Now suppose prime $p\mid (N-1)$.
If the group is indeed cyclic, then we must have $\alpha^{\frac{N-1}{p}} \not\equiv 1$. Don't we?
In particular if this holds for every prime divisor of $N-1$, then it holds for every $k$. See Finding primitive roots.

A ok... But how do we get this formula for $S$?

I'm interpreting the size of the witness as the number of operations we have to do to verify if $N$ is composite.
That means we first have to check if our selected prime divisors are indeed prime, which would take $S(p_i)$ operations for each of them.
And then we can verify if $\alpha^{(N-1)/p_i}\equiv 1$ or not for all $i$. And it is suggested that that takes $\log^2 N$ operations in total.

We would check if $\alpha^{\frac{N-1}{p_1}}, \dots, \alpha^{\frac{N-1}{p_k}} \neq 1$.
If all these inequalities hold, don't we deduce that $N$ is a prime? (Thinking)

It's the other way around.
If we can find even one $p_i$ such that $\alpha^{\frac{N-1}{p_k}} \neq 1$, we deduce that $N$ is composite.
Otherwise it's inconclusive, although we consider it likely that $N$ might be a prime. (Nerd)

Given the witness $(\alpha, p_1, ..., p_k)$, we just need to make $k$ operations, namely to find the powers $\alpha^{\frac{N-1}{p_j}}, j=1, \dots, k$, don't we?

Indeed. And we have $k = \log N$.
How would we verify if $\alpha^{\frac{N-1}{p_j}}\equiv 1$ for a particular $p_j$? (Wondering)

 

[evinda]

The 'iff' is misplaced in your statement. It should be 'if $N$ is a prime'.

A ok...

Can we find an example of a cyclic group with $N$ composite?

$\mathbb{Z}_8$.

The logical inversion of 'if A then B' is 'if not B then not A', isn't it?
What do we get if we apply that to 'if $N$ is prime then $(\mathbb{Z}/N \mathbb{Z})^{\ast}$ is cyclic'? (Wondering)

If $(\mathbb{Z}/N \mathbb{Z})^{\ast}$ is not cyclic, then $N$ is not prime.

So if we cannot find an $\alpha$ such that $\alpha^{N-1} \equiv 1 \pmod{N}$ and $\alpha^k \not\equiv 1 \pmod{N}, k=1, \dots, N-2$
then we deduce that $N$ is not a prime. Right?

We want to know if we can find an element $\alpha$ such that $\alpha^k \not\equiv 1 \pmod N$ for $k=1,..., N-2$.
Btw, such an element is called a primitive root. Do you perchance have any notes on that?

At the article I am reading now, there aren't any notes on that.

Anyway, instead of checking each and every $k$, we're trying to be smart about it.
We already know that $\alpha^{N-1}\equiv 1$.
Now suppose prime $p\mid (N-1)$.
If the group is indeed cyclic, then we must have $\alpha^{\frac{N-1}{p}} \not\equiv 1$. Don't we?

Yes, $N-1$ should be the smallest integer for which $a^{d}=1 \pmod{N}, d \in \mathbb{Z}$, right?

In particular if this holds for every prime divisor of $N-1$, then it holds for every $k$. See Finding primitive roots.

I haven't really understood why this is true... (Sweating)

I'm interpreting the size of the witness as the number of operations we have to do to verify if $N$ is composite.
That means we first have to check if our selected prime divisors are indeed prime, which would take $S(p_i)$ operations for each of them.
And then we can verify if $\alpha^{(N-1)/p_i}\equiv 1$ or not for all $i$. And it is suggested that that takes $\log^2 N$ operations in total.

So to find some power, we use repeated squaring, right?
So is the time complexity the following?

$$\sum _{i=1}^{\log{N}} \log{\frac{N-1}{p_i}}=\sum_{i=1}^{\log{N}} [ \log{(N-1)}-\log{p_i}]= \log{N} \log{(N-1)}- \sum_{i=1}^{\log{N}} \log{p_i}=\log{N} \log{(N-1)}-[\log{p_1}+ \dots+ \log{p_{\log N}}]=\log{N} \log{(N-1)}-\log{(N-1)}=O(\log^2 N)$$

It's the other way around.
If we can find even one $p_i$ such that $\alpha^{\frac{N-1}{p_k}} \neq 1$, we deduce that $N$ is composite.

Why does this hold? Couldn't it be that $\alpha$ is just not the generator?

How would we verify if $\alpha^{\frac{N-1}{p_j}}\equiv 1$ for a particular $p_j$? (Wondering)

We find $\alpha^{\frac{N-1}{p_j}}$ using repeated squaring and so we can check if the result is $1$ or not, right?

 

[I like Serena]

A ok...

$\mathbb{Z}_8$.

If $(\mathbb{Z}/N \mathbb{Z})^{\ast}$ is not cyclic, then $N$ is not prime.

So if we cannot find an $\alpha$ such that $\alpha^{N-1} \equiv 1 \pmod{N}$ and $\alpha^k \not\equiv 1 \pmod{N}, k=1, \dots, N-2$
then we deduce that $N$ is not a prime. Right?

My mistake. (Blush)
The statement is correct after all: $(\mathbb Z/N\mathbb Z)^*$ is cyclic of order $N-1$ iff $N$ is prime.
That's because the order $N-1$ is part of the statement.

So if we can prove that $(\mathbb Z/N\mathbb Z)^*$ is cyclic of order $N-1$, it follows that $N$ is prime.

Btw, $\mathbb{Z}_8$ is not cyclic, although $\mathbb{Z}_{10}$ is.
And it's cyclic of order 4 and not of order 10-1, implying that 10 is indeed not a prime number as expected.

Yes, $N-1$ should be the smallest integer for which $a^{d}=1 \pmod{N}, d \in \mathbb{Z}$, right?

Yep.

I haven't really understood why this is true... (Sweating)

I actually intended to refer to the algorithm to find primitive roots as an explanation. (Angel)
But let's see what the proof would look like.

We need to find an element $\alpha$, such that its order is $N-1$, yes?
If we have one with $\alpha^{N-1}=1$, that implies that either its order is $N-1$, or its order divides $N-1$.
Suppose the order is actually $d \mid (N-1)$ and $d<N-1$.
Then $d$ must divide one of the $\frac{N-1}{p_i}$ shouldn't it?
So if $\alpha^d = 1$, we must also have that $\alpha^{\frac{N-1}{p_i}}=1$.
Taking the logical inversion, it follows that if $\alpha^{\frac{N-1}{p_i}}\ne 1$ for every $i$, that the order of $\alpha$ is not less than $N-1$.

So if $\alpha^{\frac{N-1}{p_i}}\ne 1$ for every $i$, then the order of $\alpha$ is $N-1$. (Nerd)

So to find some power, we use repeated squaring, right?
So is the time complexity the following?

$$\sum _{i=1}^{\log{N}} \log{\frac{N-1}{p_i}}=\sum_{i=1}^{\log{N}} [ \log{(N-1)}-\log{p_i}]= \log{N} \log{(N-1)}- \sum_{i=1}^{\log{N}} \log{p_i}=\log{N} \log{(N-1)}-[\log{p_1}+ \dots+ \log{p_{\log N}}]=\log{N} \log{(N-1)}-\log{(N-1)}=O(\log^2 N)$$

What are we summing here? (Wondering)

Why does this hold? Couldn't it be that $\alpha$ is just not the generator?

You're quite right. I made a mistake.
If we can prove that they are all different from 1, while we do have that $\alpha^{N-1}=1$, then it follows that $N$ is prime.

We find $\alpha^{\frac{N-1}{p_j}}$ using repeated squaring and so we can check if the result is $1$ or not, right?

Indeed. How many squarings would we have to do?

 

[evinda]

My mistake. (Blush)

No problem...

The statement is correct after all: $(\mathbb Z/N\mathbb Z)^*$ is cyclic of order $N-1$ iff $N$ is prime.
That's because the order $N-1$ is part of the statement.

So if we can prove that $(\mathbb Z/N\mathbb Z)^*$ is cyclic of order $N-1$, it follows that $N$ is prime.

Btw, $\mathbb{Z}_8$ is not cyclic, although $\mathbb{Z}_{10}$ is.
And it's cyclic of order 4 and not of order 10-1, implying that 10 is indeed not a prime number as expected.

I see... (Nod)

We need to find an element $\alpha$, such that its order is $N-1$, yes?
If we have one with $\alpha^{N-1}=1$, that implies that either its order is $N-1$, or its order divides $N-1$.
Suppose the order is actually $d \mid (N-1)$ and $d<N-1$.
Then $d$ must divide one of the $\frac{N-1}{p_i}$ shouldn't it?
So if $\alpha^d = 1$, we must also have that $\alpha^{\frac{N-1}{p_i}}=1$.
Taking the logical inversion, it follows that if $\alpha^{\frac{N-1}{p_i}}\ne 1$ for every $i$, that the order of $\alpha$ is not less than $N-1$.

So if $\alpha^{\frac{N-1}{p_i}}\ne 1$ for every $i$, then the order of $\alpha$ is $N-1$. (Nerd)

Ah I see! (Smirk)

What are we summing here? (Wondering)

I was trying to find the time needed to compute the values $\alpha^{\frac{N-1}{p_1}}, \dots, a^{\frac{N-1}{p_k}}$.

Using repeated squaring, don't we need time $O\left(\log{\frac{N-1}{p_i}}\right)$ to compute $\alpha^{\frac{N-1}{p_i}}$ ?

If so, then to compute the $k$ values , $\alpha^{\frac{N-1}{p_1}}, \dots, a^{\frac{N-1}{p_k}}$, we need

$$\sum_{i=1}^k \log{\frac{N-1}{p_i}} \leq \sum _{i=1}^{\log{(N-1)}} \log{\frac{N-1}{p_i}} =\sum_{i=1}^{\log{(N-1)}} [ \log{(N-1)}-\log{p_i}] \\ = \log^2{(N-1)}- \sum_{i=1}^{\log{(N-1)}} \log{p_i}=\log^2{(N-1)}-[\log{p_1}+ \dots+ \log{p_{\log{(N-1)}}}] \\=\log^2{(N-1)}-\log{(N-1)}=O(\log^2 N)$$

time, don't we?

You're quite right. I made a mistake.
If we can prove that they are all different from 1, while we do have that $\alpha^{N-1}=1$, then it follows that $N$ is prime.

(Nod)

Indeed. How many squarings would we have to do?

As many as the result of the sum above? Or not? (Thinking)

 

[I like Serena]

I was trying to find the time needed to compute the values $\alpha^{\frac{N-1}{p_1}}, \dots, a^{\frac{N-1}{p_k}}$.

Using repeated squaring, don't we need time $O\left(\log{\frac{N-1}{p_i}}\right)$ to compute $\alpha^{\frac{N-1}{p_i}}$ ?

If so, then to compute the $k$ values , $\alpha^{\frac{N-1}{p_1}}, \dots, a^{\frac{N-1}{p_k}}$, we need

$$\sum_{i=1}^k \log{\frac{N-1}{p_i}} \leq \sum _{i=1}^{\log{(N-1)}} \log{\frac{N-1}{p_i}} =\sum_{i=1}^{\log{(N-1)}} [ \log{(N-1)}-\log{p_i}] \\ = \log^2{(N-1)}- \sum_{i=1}^{\log{(N-1)}} \log{p_i}=\log^2{(N-1)}-[\log{p_1}+ \dots+ \log{p_{\log{(N-1)}}}] \\=\log^2{(N-1)}-\log{(N-1)}=O(\log^2 N)$$

time, don't we?

As many as the result of the sum above? Or not? (Thinking)

Ah okay.
Yes.
Btw, wouldn't we also need to calculate $\alpha^{N-1}$? And verify that it is equal to 1? (Wasntme)

 

[evinda]

Ah okay.
Yes.
Btw, wouldn't we also need to calculate $\alpha^{N-1}$? And verify that it is equal to 1? (Wasntme)

Oh yes. For that, we need $O(\log{N})$ time. And we have that $\log{N}=O(\log^2{N})$. Right?

 

[I like Serena]

Oh yes. For that, we need $O(\log{N})$ time. And we have that $\log{N}=O(\log^2{N})$. Right?

Yep. (Nod)

 

[evinda]

But we suppose at the induction step that $S(\log{p_i})=(\log{p_i})^c$ and so we want to prove that $S(\log{N})=(\log{N})^c$. So far, we have proven that $S(\log{N})=O((\log{N})^c)$.
How can we show that $S(\log{N})=(\log{N})^c$? (Thinking)

 

[I like Serena]

But we suppose at the induction step that $S(\log{p_i})=(\log{p_i})^c$ and so we want to prove that $S(\log{N})=(\log{N})^c$. So far, we have proven that $S(\log{N})=O((\log{N})^c)$.
How can we show that $S(\log{N})=(\log{N})^c$? (Thinking)

We still hadn't clarified what the size of a witness is exactly.
My current interpretation is that it's the time complexity as function of the number of primes in $N-1$.
And that time complexity is $O((\log{N})^c)$.
More specifically, I think that $S(n\text{ primes in }(N-1)) = n^c$ means that the time complexity is $O(n^c)$. (Thinking)

 

[evinda]

We still hadn't clarified what the size of a witness is exactly.

$(\alpha, p_1, \dots, p_k)$ is the witness.

So, couldn't it also be the size of $\alpha$ plus the size of the certificates of the $p_i$s ?

If so, then $$S(\log{N})= S(\log{p_1})+ \dots+ S(\log{p_k})+ \log{N}= (\log{p_1})^c+ \dots+ (\log{p_k})^c+ \log{N} \leq (\log{p_1}+ \dots+ \log{p_k})^c+ \log{N}=(\log{(N-1)})^c+ \log{N}$$

How can we formally show that the latter is $\leq (\log{N})^c$ without using big $O$ notation? (Thinking)

 

[I like Serena]

$(\alpha, p_1, \dots, p_k)$ is the witness.

So, couldn't it also be the size of $\alpha$ plus the size of the certificates of the $p_i$s ?

If so, then $$S(\log{N})= S(\log{p_1})+ \dots+ S(\log{p_k})+ \log{N}= (\log{p_1})^c+ \dots+ (\log{p_k})^c+ \log{N} \leq (\log{p_1}+ \dots+ \log{p_k})^c+ \log{N}=(\log{(N-1)})^c+ \log{N}$$

How can we formally show that the latter is $\leq (\log{N})^c$ without using big $O$ notation? (Thinking)

Didn't we establish that:
$$S(\log{N})= \log^2{N} + S(\log{p_1})+ \dots+ S(\log{p_k})+ \log{N}=\log^2{N} + (\log{p_1})^c+ \dots+ (\log{p_k})^c \leq (\log{p_1}+ \dots+ \log{p_k})^c+ \log{N}=\log^2{N} + (\log{(N-1)})^c$$
(Wondering)

It follows that:
$$S(\log{N}) = \log^2{N} + (\log{(N-1)})^c < \log^2{N} + \log^c{N} \le 2(\log N)^{\max(2,c)} = C(\log N)^{c'}$$
In other words:
$$S(\log{N}) = O((\log N)^{c'})$$
(Thinking)

 

[evinda]

Didn't we establish that:
$$S(\log{N})= \log^2{N} + S(\log{p_1})+ \dots+ S(\log{p_k})+ \log{N}=\log^2{N} + (\log{p_1})^c+ \dots+ (\log{p_k})^c \leq (\log{p_1}+ \dots+ \log{p_k})^c+ \log{N}=\log^2{N} + (\log{(N-1)})^c$$
(Wondering)

It follows that:
$$S(\log{N}) = \log^2{N} + (\log{(N-1)})^c < \log^2{N} + \log^c{N} \le 2(\log N)^{\max(2,c)} = C(\log N)^{c'}$$
In other words:
$$S(\log{N}) = O((\log N)^{c'})$$
(Thinking)

I see... Thank you very much! (Smirk)