Need a good primer on Random Prime Number Generation?

Answer 1

An easy way to generate random primes is to start with a random number in the specified range, then count down from there, checking each number for primality.

A good primality test is the Miller-Rabin test. Coding up this algorithm requires a bit of work, but the results are worth it. It can determine with arbitrarily high accuracy whether or not a huge number is prime. It's a probabilistic test, meaning it does not prove primality, but the more times a number passes the test, the more likely it is to be prime. The accuracy is such that only about 1/4 of the remaining non-prime numbers will past each test. So, after 10 tests, if your number passes (is declared prime), the chances of it actually being composite are only 1/4^10, which is extremely small. The test also runs very quickly, even when testing huge numbers.

The algorithm would go like this:
1. User chooses number range.
2. Pseudo-random generator chooses a number in that range.
3. Run 10 to 20 Miller-Rabin trials.
4. If it passes all trials, it is *almost* certainly prime, so report the number.
5. If it fails even a single test, it is proven composite, so decrement the number by 1 and go to step 3.

Answer 2

Not sure if you want code (programming) or something else. But here is what might help.

http://generator-number-prime.qarchive.org/

If you want code, here is a javaScript script

http://webdeveloper.earthweb.com/webjs/jsmath/item.php/240771_viewit