We know that composite integers can be expressed as a difference of squares. $$N=a^2-b^2=(a-b)\times(a+b)$$

So if we wanted to generate primes using a difference of squares, we could simply multiply one of the square above by a non-square $(2,3,\ldots)$. We get $$N=a^2-m\times b^2$$

There are two simple precautions to take.

  1. Make sure that the two terms have opposite parity; and
  2. Make sure that the two terms do not share a common factor greater than $1$.

We provide a simple example to illustrate how the algorithm works. $$N_{1}=13^2 - 2\times 1^2=167$$
$$N_{2}=13^2 - 2\times 3^2=151$$ etc... We don't always get a prime, like in $$N_{3}=13^2 - 2\times 5^2=119=7\times 17$$ but we often do. We can continue subtracting $$2\times b^2$$ until we get a negative number. Even the negative numbers can often be prime. And we can multiply either square by the multiplier m and we can use any multiplier. It does not have to be $2$.

So the question is, how good is this simple way to generate primes? We obviously have to run a primality test to verify if the numbers generated are indeed primes.

  • 3
    $\begingroup$ It's very simple. Is there a reason to suspect that this would be better than picking random numbers to test? $\endgroup$ – Morgan Rodgers Dec 18 '16 at 23:08
  • $\begingroup$ Not better, just another way to do things. One could test both and see which one is faster in finding a prime. $\endgroup$ – user25406 Dec 19 '16 at 0:39
  • 2
    $\begingroup$ You would need to analyze probabilities of finding a prime for each method; just running a test isn't enough to say one is better than the other (you might get lucky with your algorithm by choosing a particular $a$ and $b$). So if there is not a reason to think it is a more efficient way to find primes than just choosing randomly, what purpose does it serve? $\endgroup$ – Morgan Rodgers Dec 19 '16 at 3:41
  • 2
    $\begingroup$ You are asking "is this method any good?". So my question to you is, "do you have a reason to think it is a good method?" If you want to convince someone that the analysis is worthwhile, you should at least be able to say why you think this might be a good method. $\endgroup$ – Morgan Rodgers Dec 19 '16 at 13:56
  • 2
    $\begingroup$ And for your question, no I am not saying we should ignore new ways to do something because we already have one method. But if it cannot be convincingly shown to be better than guessing at random, then yes we should discard it. $\endgroup$ – Morgan Rodgers Dec 19 '16 at 13:58

Notice that for example a number $151$ you have used can be written also as:

$13^2-2 \cdot 3^2=151$

$13^2-18 \cdot 1^2=151$

Looking for prime number $41$ you could go checking $a^2$:


$10^2-5 \cdot 4^2=10$

$11^2-5 \cdot 4^2=41$

In my opinion if you continue subtracting $m \cdot b^2$ or even checking for conditions whether a number is prime or not, it might be a problem locating numbers between $(N, 2N)$, where $N$ is $1000$-digit long or more.

  • $\begingroup$ 10^2 - 5.4^2 = 10, does not qualify because the two squares have a common factor. We should avoid that situation as specified above. I haven't really thought about to adapt this method to finding a prime between (N, 2N). But the obvious starting point is to take a square between N and 2N and start subtracting m*b^2. One of the number has to be a prime but if it is the only prime in that interval, then it may take some time to find it. $\endgroup$ – user25406 Dec 19 '16 at 0:36
  • $\begingroup$ if I were looking for prime 41, I wouldn't have chosen 11^2 as the main square. I would have chosen a smaller square, something like 7^2-2*2^2=41. $\endgroup$ – user25406 Dec 19 '16 at 0:57
  • $\begingroup$ The second example was to show, that you don't know what square to start with ( also $10$ is not a prime number ). Going through iterations is time consuming. $\endgroup$ – usiro Dec 19 '16 at 18:12
  • $\begingroup$ Sure, iterating is time consuming but picking a number at random is no less time consuming because there is no guarantee that the first pick will be a prime. Looking for a "prime in general" and a very specific prime ( 41 in your example) are two different issues. Looking for a specific prime is a lot more complicated and is not the purpose of this method. And I don't know of any method that can find a specific prime. After all that would mean we know how to get the next prime which is still an open problem. $\endgroup$ – user25406 Dec 19 '16 at 18:47
  • 2
    $\begingroup$ I think your method should have more specific purpose. Where can I apply this method? or When can I use it? I am currently working on some problem using Fermat's factorisation. If I see that applying extra term, which is $m$ in your case can help me in some way, I will let you know. $\endgroup$ – usiro Dec 19 '16 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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