How are the large prime numbers generated ? If they’re so hard to factor, why aren’t they also difficult to generate?
It’s very easy to factor a prime number. The factors are 1 and itself. 
What’s difficult is finding a fast way to find the prime factors of a composite number. If you take the product of two really big primes, for example, finding the prime factors of the product takes a really long time.
I wrote some code that creates a public/private key pair for RSA. It takes several minutes to run even though pretty much all of that time is in finding a prime number of proper length. So no, it’s not fast. 
As for how you generate it, essentially you just pick a random number and keep adding one until you’ve found a number that passes a prime number test (or keep trying random numbers).
Thank you. But how are the large primes generated (i.e., before they’re multiplied)?
If you pick a random number and keep adding one until you find a prime, doesn’t that mean that there’ll be a lot of overlap among primes generated by your code? How many primes are in that space?
- Decide how many bits you want it to have.
- Set the high and low bit to 1.
- Set the other bits randomly.
- Check to see if it’s a prime number.
- If so, you’re done. Otherwise, add 2 and go to step 4.
Each time you want to generate a new random number, you start in a random spot, not where you last left off.
If you choose your start point randomly for each new prime, there’s no particular reason that two values would end up near each other. For my code, rather than adding one each time, I picked a new random number, but I probably didn’t need to.
As for how many primes there are on average in a region, there is a formula to determine that,* but since you have to find a prime, it doesn’t really matter how hard it is. You still have to do it.
- “Roughly speaking, the prime number theorem states that if a random number nearby some large number N is selected, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N.” - Wikipedia
You can generate them yourself with an algorithm like Erastosthenes’ Sieve (which also takes a little while) or you can just pick some from a known list.
For example, if I pick known primes 9,879,452,447 and 9,879,454,831, the result is 97,603,604,205,148,921,457 which would take quite a while to factor.
If you used a known list, wouldn’t the composite number be fairly easy to factor?
Since no even numbers are prime, you can increase the speed of this by adding two instead of one. (and then there is no need to test for 2 as a factor)
Lots of faster ways to find primes, BTW.
ETA:No even numbers except 2 are prime.
Not necessarily, if the list is large. It’s really quick to pick some random entry from a big list, while it takes a long time to check data against every entry in the list.
The Prime Counting Function allows us to calculate the number of primes that are less than a given number x. Public-key cryptography now typically uses keys that are 512 bits in length, meaning that we would potentially have to check all primes less than 2^512, which is going to be a fairly large number, approximately equal to 2^512 / ln(2^512), which is 3.78 * 10^151. Even if the list is known, the problem can still be impracticably difficult if the list is long enough, which is true in this case.
Public key cryptography hasn’t used 512 bit keys since 1990.
In Wikipedia’s RSA article, they say:
Back to the OP’s question:Punoqllads about covered it, but skimmed over the testing step. Primes are hard to test for mostly because there are a huge number of possible factors to try. See Wikipedia again for info on that.
One doesn’t need the calculation details to grasp the concept: Some reversible processes are easier one direction than the other. For example, it’s much easier to square 7777 than to find the square root of 60481729. Or, it’s much easier to exit a parallel-parking spot than to park there in the first place. 
Technical question I’m too lazy (or stupid) to Google for: Some primality tests will miscall primes 0.000001% of the time. What happens if you feed such a pseudo-prime into the encryption algorithms?
The technical term for this is a “trapdoor function”: It’s easy to fall in (multiply two big numbers) but difficult to climb back out (factor one huge number).
The encryption still works fine, but it’s easier to break.
(Missed the edit.)
The Greatest Common Factor test will find a factor half the time (for large numbers), so you can apply it repeatedly to reach any probability you like that your candidate number is prime.
What’s “the Greatest Common Factor test”?