Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
1  

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer

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?

share|improve this answer
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.. –  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 :

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.