Primality test of quadratic polynomials

Question

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

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

Answer 2

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.