One old way to test a number quickly for primality is based on Fermat's Little Theorem. If n is a prime number, then for any b between 2 and n-1, b^n must equal 1 modulo n.
Sometimes this will be true for some values of b even if n is not prime. There are even some numbers, called Carmichael numbers, for which this is true for all values of b, except those few values of b which are factors of n.
This is the Fermat test. There are two newer probabilistic primality tests which also involve trying different values of a number which we can still call b to test if n is prime. There are no values of n which are not prime that will nearly always fool these tests the way Carmichael numbers pass the Fermat test. These tests are the Solovay-Strassen and Miller-Rabin tests. The Miller-Rabin test is more complicated to understand than the Solovay-Strassen test, but it is also somewhat quicker and indicates the compositeness of some composite n for additional values of b, while never failing to indicate the compositeness of a value of n that is composite for any b for which the Solovay-Strassen test will show n to be composite, and is thus superior.
For the Solovay-Strassen algorithm, one chooses b within the range 1 to n-1. One tests to see if b is relatively prime to n; if not, clearly n isn't prime; this needs to be tested since the other half of the test will not work in this rare case. A function of b and n, called J(b,n), must also equal b^((n-1)/2) modulo n.
J(b,n) is called the Jacobi symbol of b and n. For the values of b and n which we will be using, where b is less than n, and b and n are relatively prime, J(b,n) will always be either 1 or -1, and it can be calculated as follows:
J(1,n) is 1 for any n.
If b is an even number, and n is an odd number, J(b,n)=J(b/2,n) * ((-1)^((n*n-1)/8)).
Otherwise, J(b,n)=J(n mod b,b) * ((-1)^((b-1)*(n-1)/4)).
One reference stated that this method for calculating J only worked when n was odd. Since the third alternative in the recursion process sets n equal to b, and b doesn't have to be odd, it would break down: instead, the condition that n must be odd needs to be applied specifically to the second alternative (since n squared minus 1 won't be divisible by 8 when n is even) where it belongs.
For this test, one chooses b to be between 2 and n-2.
m is equal to n-1 divided by 2 as many times as is possible (thus, m is odd).
Let t be equal to b^m modulo n.
If t is either 1 or n-1, n passes the test for b.
Otherwise, do the following for a maximum of s times, where s is the number of times n-1 was divided by 2 to get m or until n either passes or fails, set the new value of t to be t squared modulo n. If t becomes 1 as a result, n fails the test for b; if it becomes n-1 as a result, n passes the test for b, and if neither happens during the s attempts, n fails.
As I understand the references I used, one omits immediate failure when t becomes 1, and another omits limiting the test to s trials. I have been informed via E-mail that the limitation to s trials cannot be omitted, as t can loop indefinitely in a sequence including neither 1 nor n-1.
I cannot claim sufficient expertise to vouch for the accuracy of my attempt at a description of the Miller-Rabin probabilistic primality test at this time. There is a more complicated primality test which is still much quicker than factoring which can be used to make certain that a number is prime.
Another issue to deal with in selecting prime numbers to use with RSA is to make sure that one chooses them completely randomly; if one's method of search is not random, it could make it easier for someone else to find the number you are using by some type of search. (Of course, the numbers involved are so large that a brute-force search for factors is not a real threat, but possibly knowing something about the primes used might be used in conjunction with a better factoring algorithm.)
The simplest way to choose a prime at 'random' would be to choose a large number at random, and then count upwards from it until you come to a prime number, of course skipping the even numbers.
One can do a bit better than that, by skipping all numbers divisible by 2, 3, 5 and 7 in blocks of 210 numbers, for example.
But then the chance of choosing a prime number is proportional to the distance between it and the next lower prime number. This can be avoided as follows: choose a large number, N, at random, and look for prime numbers of the form 210*N+k, where the values of k are chosen from a table of the numbers from 0 to 209 that are not divisible by 2, 3, 5, or 7, shuffled into a random order. One then continues by adding one to N.
If one is looking for a prime number with special properties, or a very large prime number, so that these primes are so rare there is less than one of them in every 210 numbers, one can go further yet. One can begin by choosing a random starting point within the table for the values of k used. And before using a new value of N, one can encipher its last 64 bits using DES. In that way, one will hop around an area of numbers 210*(2^64) consecutive numbers in size in an order that is haphazard, although not truly random. But the fact that one stays in blocks of 210 numbers does not affect the fact that the first number in the area one is hopping around in that one picks will be random.
Of course, one must start completely over before looking for the second prime. Also, two primes very close together are easily factored by a simple method also due to Fermat. Since (a+b) times (a-b) equals a squared minus b squared, the product of two numbers close together is equal to a large square number minus a much smaller one. The method based on this was the first one to be significantly faster than intelligently applied trial division.