Primality Test for Safe Primes

201 Views Asked by At

Is this proof acceptable ?

Theorem

Let $N$ be of the form $N=2p +1$ with $p$ prime , then

$N$ is prime iff $N \mid 2^{2p}-1$

Proof

In one direction , if $2p+1$ is a prime then by Fermat Little Theorem we have :

$2^{2p} \equiv 1 \pmod N$ , hence $N \mid 2^{2p}-1$ .

Conversely , let $N$ be a factor of $4^p-1$ .

If $p=2$ then :

$N \mid 4^2-1$ and $N=5$ , so $N$ is prime .

If $p >2$ , then :

Suppose that $2p+1$ is composite and let $q$ be it's least prime factor .

Then , $4^p \equiv 1 \pmod q$ , and so :

$\operatorname{ord_q(4)} \mid p$ and $\operatorname{ord_q(4)} \mid q-1$ , hence

$p \mid q-1$ , and therefore $q> p$ .

It follows : $(2p+1)+1 > q^2 > p^2$ ,

which is contradiction since $p>2$ , hence $N$ must be prime .

1

There are 1 best solutions below

0
On BEST ANSWER

First, I might change what you wrote from

It follows : $(2p+1)+1 > q^2 > p^2$

to

If $N$ is composite, it follows : $(2p+1)+1 > q^2 > p^2$

The claim might be true, but I think there is a problem with this argument. What if $q$ (the smallest prime factor of $N=2p+1$) is $3$? Then in the second part of the argument where we assume $N$ is a factor of $4^p-1$, it is still true that $4^p\equiv1\mod q$, and this does imply that $\operatorname{ord}_{q}(4)\mid p$. But your argument then proceeds as if $\operatorname{ord}_q(4)=p$. With $q=3$, actually $\operatorname{ord}_q(4)= 1$. There is no implication then that $q>p$.

If $N$ is additionally not divisible by $3$, then maybe your argument works. (That is, if $N=6p\pm1$.)

If $3$ is the smallest prime divisor of $N$, then either $N=3^k$, or you can modify your argument to let $q$ be the second smallest prime divisor of $N$. In the latter case, you still get that this $q$ is greater than $p$. If $N$ is not prime, then your next-to-last line becomes $(2p+1)+1>3q>3p$, which is still a contradiction.

This leaves the case $N=3^k$, where we are still assuming $N$ is a factor of $4^p-1$. We know in this case that $N$ is not prime. So your claim (in its full totality) hinges on $p=\frac{3^k-1}{2}$ not being prime when $3^k$ divides $4^p-1$.