From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on a relatively slow computer, and it still completed in only seconds. How can my computer generate random primes so quickly, when this is considered one of the most difficult problems in mathematics?
Generating large primes is not difficult. For example, using PARI/GP,
generates a random 100-digit prime in about 2 milliseconds. An implementation which need not follow a strict uniform distribution could be much faster. For full cryptographic strength, see FIPS 186-4.
The hard problem is factoring large semiprimes, not generating random semiprimes.