# How to improve this primality test?

Theorem :

If an odd number $n$ , $n > 1$ can be uniquely expressed as : $n=x^2-y^2$ ; $x,y \in \mathbb{Z}^{*}$ then

$n$ is a prime number .

Test written in Maple :

Any idea how to improve this test ?

-
I am not familiar with Maple (shame on me). But a search up to about $p/6$ could be a lot longer than searching for factors in the naive way up to $\sqrt{p}$. – André Nicolas Jan 12 '12 at 7:35
@AndréNicolas,You are right...that's why I am asking whether this test can be improved . Maybe I have missed something.. – pedja Jan 12 '12 at 7:39

While Fermat's difference of squares technique is generally not an efficient way to prove primality, as Gauss noted, one can speed up the basic brute force search by employing quadratic exclusions. Below is an example from W. Bosma and M. van der Hulst, Primality proving with Cyclotomy.

-

If $p$ is of the form $4n+1$, you can skip odd values of $x$; and if $p$ is of the form $4n+3$, you can skip even values of $x$. So you can initialize $x$ to $0$ or $1$ depending on $p$ and always advance $x$ by $2$. This would seem to be an equivalent program which runs twice as fast. I believe I understand the theorem, but it's not clear to me from inspection how the program tests for uniqueness of the expression?

-
If number is prime then $x=y+1$ , so you only need to check if there is some other representation of $p$ and that is what this program basically doing.. – pedja Jan 12 '12 at 9:04

Thanks to the Dan's and Bill's useful observations I wrote an improved version of the test so here it is :

Number of iterations in worst case is given by :

$\left \lceil \frac{p-p^2_{n+1}}{4 \cdot p_{n+1}} \right \rceil + n$

where $n$ is a number of consecutive primes in the list and $p_{n+1}$ is $(n+1)$-th prime number.

-