# Primality test of quadratic polynomials

There are some quadratic polynomials like $n^2+1$ that there exist inﬁnitely 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$.

-

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.

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

-
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