Lets prime factorize $30$:

$$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$

We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two primes. Why is this??

  • 2
    $\begingroup$ Does this answer your question? Are there any standards of multi-prime RSA key generation? $\endgroup$
    – kelalaka
    Commented Mar 19, 2020 at 12:34
  • 5
    $\begingroup$ Because RSA modulus are not just random big numbers: they are built by first sampling two primes, and then multiplying them together. $\endgroup$ Commented Mar 19, 2020 at 12:59
  • $\begingroup$ Thank you Geoffroy Couteau. Since primes are rather "unusual", especially the bigger the number, won't that leave a manageable (for a computer) amount of products to "choose" from. A hacker/decoder might have a library of prime products and will be able to look up the chosen number. $\endgroup$ Commented Mar 19, 2020 at 13:21
  • 2
    $\begingroup$ @KristianFranciscoMillaNiels see this other question $\endgroup$
    – SEJPM
    Commented Mar 19, 2020 at 13:35
  • $\begingroup$ @KristianFranciscoMillaNiels Also see the GCD Them ALL $\endgroup$
    – kelalaka
    Commented Mar 19, 2020 at 14:17

1 Answer 1


By construction, RSA moduli are the product of two large primes.

  • 1
    $\begingroup$ Or more. Depends on how the RSA moduli is generated. Muliprime RSA is a thing, we even have a multi-prime-rsa tag for it. In particular, there is provision for it in the private key format defined by PKCS#1v2.2. $\endgroup$
    – fgrieu
    Commented Apr 18, 2020 at 21:38
  • $\begingroup$ Three factors would be very useful if someone finds an ingenious method to factor products of two large primes which is useless for products of three large primes. Which is quite conceivable. $\endgroup$
    – gnasher729
    Commented Apr 19, 2020 at 9:23
  • $\begingroup$ @gnasher729: the reason usually driving the use of $f>2$ factors are (A) speed of the private key operation (using the CRT method) for a given public modulus size : when modular multiplication with $b$-bit arguments has cost proportional to $b^2$, the speedup is by a factor $f^2/4$, that is over a factor of two for $f=3$; and (B) allowing to work around a limitation on $b$ in the hardware doing fast modular arithmetic, which for a given public modulus size operates with arguments of size inversely proportional to $f$. $\endgroup$
    – fgrieu
    Commented Apr 19, 2020 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.