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?

| cite | improve this question | | | | |
  • $\begingroup$ Are you familiar with the Miller-Rabin test? $\endgroup$ – anomaly Jul 9 '15 at 17:21
  • $\begingroup$ One very fast method is using prime number tables. P. ex. primos.mat.br/2T_en.html $\endgroup$ – zoli Jul 9 '15 at 17:31
  • 1
    $\begingroup$ Factorising products of large primes is the difficult problem you are referring to, not generating large primes. $\endgroup$ – Rammus Jul 9 '15 at 17:32

Generating large primes is not difficult. For example, using PARI/GP,

randomprime([10^99, 10^100])

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.

| cite | improve this answer | | | | |
  • 2
    $\begingroup$ The number generated is a prime number with high probability, which is not guaranteed to be a prime, right? $\endgroup$ – Sisi Jul 9 '15 at 18:01
  • 2
    $\begingroup$ @Sisi: Right, unless it's smaller than 2^64 in which case it's automatically proven via Jan Feitsma's computations with 2-pseudoprimes. If you need proven primes you can use isprime -- but cryptographic 'primes' are almost never proven. $\endgroup$ – Charles Jul 9 '15 at 18:07
  • $\begingroup$ This did not really answer the question. A better explanation is here crypto.stackexchange.com/questions/71/… $\endgroup$ – qwr Apr 8 '16 at 21:38
  • $\begingroup$ @qwr I think the core of this question is not "what are efficient algorithms for generating large random primes" but "why and how is this 'most difficult problem in mathematics' the cornerstone of RSA". As such I focused on the latter. If you think something else was intended I encourage you to give an answer of your own. $\endgroup$ – Charles Apr 8 '16 at 21:47
  • $\begingroup$ @Charles My answer would be the Crypto.SE one $\endgroup$ – qwr Apr 19 '16 at 0:40

Your Answer

