Finding large primes

There are tests that cannot be fooled, one which is based on computing the so called Jacobi symbol. This is similar to the Fermat test with more than half of the numbers a < n, a and n relatively prime, that will disclose compositeness. For both tests No means composite, and Yes means composite with probability less than one half. By repeating the test m times Yes means composite with probability less than (1/2)^m.

With this we could implement an algorithm for finding the next prime when starting from s:

  Find-Next-Prime

  Input: Start number s, repetitions m.
  Output: Probable prime.

  1. Step through the odd numbers 
     starting with s

  1.1 if Prime-Fermat(s,m) andalso 
         Prime-Jacobi(s,m) 
      then print s 
      else next s.