Title: Find random prime numbers in C#

The example Probabilistically determine whether a number is prime in C# explains an algorithm for determining whether a number is prime with any desired level of certainty. After you add that method to your algorithmic toolkit, finding large prime numbers is easy. Simply pick a large random number and see if it's prime. Then repeat until you find a prime.
The following code shows how this example finds prime numbers. (I've modified it slightly to remove progress reporting statements.)

// Probabilistically find a prime number within the range [min, max]. private int FindPrime(int min, int max, int num_tests) { // Try random numbers until we find a prime. for ( ; ; ) { // Pick a random odd p. int p = Rand.Next(min, max + 1); if (p % 2 == 0) continue; // See if it's prime. if (IsProbablyPrime(p, num_tests)) return p; } }

This method enters an infinite loop. Each time through the loop, it picks a random number in the desired range. If the number is even, the loop continues with no further testing. (The primality test will determine that even numbers are not prime, but it can be slow so there's no need to be blindly stupid here. Note that the program is looking for large primes so it doesn't need to consider the value 2.)

If the number is not even, the program calls the IsProbablyPrime method described in the previous post. If IsProbablyPrime returns true, then this method returns the candidate number, which is probably prime.

Now when you need to find large primes p and q for use with the RSA algorithm, you can simply call this method twice.

There's one other important issue to think about here: how long will it take this method to find large primes? After all, this wouldn't be a very useful algorithm if it took a million years to find a prime. Fortunately the "prime number theorem" states that primes are everywhere dense. That means in every part of the number line there are a lot of primes, so it won't take you too long to pick one randomly. In one set of 10 trials, the program picked as few as 1 and as many as 23 random numbers to find a prime, but on average it needed only 10.9 random numbers to find a prime.

When the program runs, it can usually discard several non-primes very quickly. It only needs to try a couple of random tests in the IsProbablyPrime method to decide that a number is composite. When it picks a number that actually is prime, the program takes longer because it must perform all of the tests you requested to achieve the desired level of certainty.

My book Essential Algorithms: A Practical Approach to Computer Algorithms contains more information about primality testing, prime number finding, and RSA. To see a description and table of contents, go here.

Download the example to experiment with it and to see additional details.