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 ?
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 ?
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.
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?
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.