3
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    Thanks @mixedmath, Good hint! Is there any general idea for testing $an^2+bn+c$ or we should examine them case by case?2012-05-30
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.

  • 0
    Not offhand, but if $m=2n^2-1$ then $m-1=2(n+1)(n-1)$ so you get a lot of factoring.2012-05-30