Questions about proof about primality testing

In summary, the proof presented shows that primality testing is in NP by finding a witness or certificate for the group $(\mathbb{Z}/ N \mathbb{Z})^{\ast}$ being cyclic. This is done by guessing the generator $\alpha$ and the factors $p_i$ of $N-1$, verifying that $\alpha^n \neq 1$ for any $n<N-1$. The witness/certificate for this process is polynomially bounded in the size of the input, making it possible to guess and verify. Additionally, the Little theorem of Fermat is used to show that $(\mathbb{Z}/ N\mathbb{Z})^{\ast}$ is cyclic if $N$
  • #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:

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)
 
Mathematics news on Phys.org
  • #2
evinda said:
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.

evinda said:
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.

evinda said:
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)
 
  • #3
I like Serena said:
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?
I like Serena said:
Yes. We repeat the procedure for $N' = p_1$ and so on.

I see... (Nod)
I like Serena said:
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$.
 
  • #4
evinda said:
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.

evinda said:
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)
 
  • #5
I like Serena said:
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 like Serena said:
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)

I like Serena said:
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?
 
Last edited:
  • #6
evinda said:
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)
evinda said:
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.
evinda said:
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.

evinda said:
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)

evinda said:
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)
 
  • #7
I like Serena said:
The 'iff' is misplaced in your statement. It should be 'if $N$ is a prime'.

A ok...

I like Serena said:
Can we find an example of a cyclic group with $N$ composite?

$\mathbb{Z}_8$.

I like Serena said:
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?
I like Serena said:
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.
I like Serena said:
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?
I like Serena said:
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 like Serena said:
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)$$
I like Serena said:
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?
I like Serena said:
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?
 
Last edited:
  • #8
evinda said:
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.
evinda said:
Yes, $N-1$ should be the smallest integer for which $a^{d}=1 \pmod{N}, d \in \mathbb{Z}$, right?

Yep.

evinda said:
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)

evinda said:
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)
evinda said:
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.
evinda said:
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?
 
  • #9
I like Serena said:
My mistake. (Blush)

No problem...

I like Serena said:
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)
I like Serena said:
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)

I like Serena said:
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?
I like Serena said:
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)
I like Serena said:
Indeed. How many squarings would we have to do?

As many as the result of the sum above? Or not? (Thinking)
 
  • #10
evinda said:
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)
 
  • #11
I like Serena said:
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?
 
  • #12
evinda said:
Oh yes. For that, we need $O(\log{N})$ time. And we have that $\log{N}=O(\log^2{N})$. Right?

Yep. (Nod)
 
  • #13
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)
 
  • #14
evinda said:
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)
 
  • #15
I like Serena said:
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)
 
  • #16
evinda said:
$(\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)
 
  • #17
I like Serena said:
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)
 

FAQ: Questions about proof about primality testing

1. What is primality testing?

Primality testing is the process of determining whether a given number is prime or composite. A prime number is a positive integer that is only divisible by 1 and itself, while a composite number has at least one other factor besides 1 and itself.

2. Why is primality testing important?

Primality testing is important in fields such as mathematics, cryptography, and computer science. It is used to generate large prime numbers for secure encryption and decryption, and to analyze the complexity of algorithms for solving mathematical problems.

3. How is primality testing performed?

There are several different algorithms for primality testing, including trial division, Fermat's little theorem, and the Miller-Rabin test. These algorithms use various mathematical properties and techniques to determine whether a number is prime or not.

4. Can primality testing be done for any number?

In theory, primality testing can be done for any positive integer. However, as the number gets larger, the computational complexity of the algorithms also increases. This means that for extremely large numbers, it may not be feasible to perform primality testing within a reasonable amount of time.

5. Are there any efficient ways to perform primality testing?

Yes, there are efficient algorithms for primality testing, such as the AKS primality test and the Elliptic Curve primality proving algorithm. These algorithms have polynomial time complexity, making them faster than other primality testing methods for large numbers.

Back
Top