How are random numbers for RSA generated? The RSA public key encryption requires two very large prime numbers as part of its encryption process that serve as secrets. These are typically generated with cryptographically secure random number generators of some kind.

However, random number generators generate random bits; they don't specifically generate primes; and proving that a number is prime would require attempting to factor it -- the very problem that makes RSA hard.

How are the prime numbers found for use in RSA?
Very important:

Determining whether an integer is prime is significantly easier than factoring it (at least in the current state of our knowledge). We can easily determine whether integers having thousands of decimal digits are prime, but such integers are far beyond the reach of current factoring algorithms.

Now to answer your question: "plain" RSA does not specify how the prime numbers are to be generated. For any particular implementation, you would need to look at its source code or documentation to see how it does it. A popular method is the "generate-and-test" paradigm:


Generate a random number of appropriate length.
See if it is prime, using either a probabilistic or a deterministic test depending on your level of paranoia. If it is prime, you have your prime. Otherwise, go back to step 1.


A simple application of the prime number theorem can give you an estimate of the probability that the number you picked is prime (depending on its length). This is generally not the same thing as the probability that your primality test will consider it prime, however, if you are using a probabilistic test.

I'll leave it to you as an exercise to implement this in your favourite CAS (e.g., PARI/GP or Sage) and see how it works in practice.

EDIT:

The two "tricks" given in the other answer will not make any difference in most cases.


Ensuring that we only give odd numbers to the primality test is useless: any decent primality test will immediately discard even numbers, precisely so as to not waste time on them.
Adding $2$ to the previous number instead of generating a new one from scratch also does not make any difference (at least on my machine). I can't see any reason to believe it should, either.