7
$\begingroup$

I'm trying to write a program that can tell if $n^2+1$ is prime where n is in the natural numbers (sorry I don't know how to write this in proper math notation). Sure, I can take a brute force approach to check if the number is prime, but I want to check millions of values of n, so as n gets big, $n^2$ gets out of hand quickly and my computing slows down. Is there some more efficient approach to check if it's prime?

$\endgroup$
  • $\begingroup$ What algorithm are you using to test primality? $\endgroup$ – Victor Apr 12 '17 at 20:59
  • $\begingroup$ It follows from Fermat's little theorem that if $n^2+1$ is prime, then $$2^{\frac{n^2}{2}}=\pm 1 \bmod \left(n^2 +1\right)$$ $\endgroup$ – Count Iblis Apr 12 '17 at 20:59
  • $\begingroup$ If $n$ is odd, then $n^2+1$ will be even and clearly not prime. Otherwise, I think you'd have to use an algorithm to test primality. Are you asking for the best algorithm? $\endgroup$ – scott Apr 12 '17 at 20:59
  • $\begingroup$ If you want to just "predict", then Rabin-Miller may be the way to go. Each round of testing that the prime candidate passes increases your confidence on the number being prime quite a bit (but a single failed test conclusively proves that the number is composite). $\endgroup$ – Jyrki Lahtonen Apr 12 '17 at 21:04
  • $\begingroup$ You could try both suggestions found in the comments. To expand on @CountIblis's solution, you could perform modular exponentiation logarithmically and get a reasonably fast sure answer to your query. $\endgroup$ – Victor Apr 12 '17 at 21:07
6
$\begingroup$

One very fast probabilistic primality test is the Miller-Rabin test.

Here is a working online example of the Miller-Rabin test that would help you appreciate the speed of primality testing using this algorithm.

You can also install PARI/GP and run something like this:

for (n=1,1000000,if(isprime(n^2+1),print(n)))

It's incredibly fast; testing one million values of $n$ takes less than a minute. PARI/GP relies (in part) on the Miller-Rabin test for primality testing.

Note: Under some conditions, the Miller-Rabin test can work as a deterministic primality test (i.e. it will give you a guaranteed answer whether the input number is prime or composite). See e.g. OEIS sequence A014233: smallest odd numbers for which Miller-Rabin test on bases $\le n$-th prime does not reveal compositeness. Essentially, OEIS A014233 gives you a bound below which you can use the Miller-Rabin test deterministically. For example, if you run the test for every prime "base" parameter up to 41, then the test will correctly determine primality of any odd input number up to 3317044064679887385961981.

$\endgroup$
  • $\begingroup$ How confident is this test? I need 100% confidence because if I'm testing 100 million numbers, just one incorrect answer would ruin my calculations. $\endgroup$ – Ryan Apr 12 '17 at 21:53
  • $\begingroup$ If you are testing numbers that have at most 24 decimal digits, then you can use the Miller-Rabin test deterministically, using 13 rounds of the test with prime "bases" 2, 3, 5, 7, ..., 41. If none of the 13 calls reveal compositeness, then your input is guaranteed to be prime; see OEIS A014233. $\endgroup$ – Alex Apr 12 '17 at 21:59
  • $\begingroup$ @Ryan I am also a PARI/GP user, if your number is small, lets say, less than $12$ digits, the command "isprime(n,2)" always gives a $100$% correct answer and is not much slower. Even for $100$-digit numbers you get a $100$% correct result in less than a second. So, my suggestion clearly is to use this routine. $\endgroup$ – Peter Apr 13 '17 at 22:15

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.