- #1
evinda
Gold Member
MHB
- 3,836
- 0
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:
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 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)