Primality test for numbers of form 10^n + k

I have some numbers of form 10^N + K, where N is about 1000, and K is really small (lower than 500). I want to test these numbers for primality. Currently I'm using Fermat's test by base 2, preceded by checking small factors (<10000).

However, this is rather slow for my purposes. Is there any algorithm quicker than that? Can this special form be exploited somehow?

Also, maybe开发者_如何转开发 if two numbers differ only in K, is it possible to test these two numbers a bit quicker?

---

If K has a factor of either 2 or 5 then 10^N + K is composite. This allows testing a small number quickly. Large primes are all such that P mod 6 = 1 or 5. You can use this to eliminate 2/3 of possible K values. With a little work you can set up a 2-4 wheel to avoid a lot of division:

increment <- either 2 or 4 as required
repeat
  K <- K + increment
  increment <- 6 - increment
  if (K mod 5 = 0) then 
    continue 
  endif
until (isPrime(10^N + K) or (K > 500))

Trial factoring up to 10,000 if fine. Are you building a list of the primes up to 10,000 first? Use Eratosthenes' Sieve to create the list and just read off numbers.

Running a Fermat Test base 2 is a good start, it finds a lot of composites reasonably quickly.

After that you need to implement the probabilistic Miller-Rabin test, and run it enough times that it is more probable your hardware has failed rather than the number is composite.

---

Also, maybe if two numbers differ only in K, is it possible to test these two numbers a bit quicker?

To check the primes in a relatively small interval like [10^N+K₁, 10^N+K₂] you can use the sieve of Erathostenes to check for divisibility by small numbers.

The remaining prime candidates can then be checked by a probabilistic test like Miller-Rabin.