Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are some quadratic polynomials like $n^2+1$ that there exist infinitely many integers $n$ such that their value is either prime or the product of two primes (if I am right!).

I wanted to know if there are any special efficient primality test methods for these kinds of polynomials. The cases that I'm curious about are: $n^2+1$ and $2n^2-1$.

share|cite|improve this question
up vote 1 down vote accepted

For the case $n^2 + 1$, for special values of $n$ it is very quick to use Pollards $\rho - 1$ algorithm. In particular, if you can guarantee that $n$ is B-powersmooth for some reasonably sized B.

I happen to have written up a brief expostion about this algorithm on my blog, in a TeXed-but-in-a-way-incompatible-to-anything-else format.

Analogously, the $2n^2-1$ case will be quickly factorable for special values of $n$ using Pollards $\rho + 1$ or William's $p + 1$.

But that's all I see right off.

share|cite|improve this answer
Thanks @mixedmath, Good hint! Is there any general idea for testing $an^2+bn+c$ or we should examine them case by case? – saeedn May 30 '12 at 10:38

If you have a look at any collection of primality tests (say, on Wikipedia) you'll find that some of them rely on the factorization of $m-1$ to test/prove the primality of $m$. Well, those tests should have a leg up for numbers of the form you are asking about.

share|cite|improve this answer
Thanks, I briefly looked at them. Proth's test does not help me I think, but Lucas test is suitable for $n^2+1$. Can you provide me a link that shows a efficient method for $2n^2-1$? – saeedn May 30 '12 at 10:27
Not offhand, but if $m=2n^2-1$ then $m-1=2(n+1)(n-1)$ so you get a lot of factoring. – Gerry Myerson May 30 '12 at 11:16

Your Answer


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.