0
$\begingroup$

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 :

enter image description here

Any idea how to improve this test ?

  • 1
    http://en.wikipedia.org/wiki/Quadratic_sieve2012-01-12

3 Answers 3

0

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

enter image description here

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.

1

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?

  • 1
    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..2012-01-12
1

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.enter image description here enter image description here