# Prime Factorization in RSA always leads to the product of two primes?

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??

• Does this answer your question? Are there any standards of multi-prime RSA key generation? – kelalaka Mar 19 '20 at 12:34
• Because RSA modulus are not just random big numbers: they are built by first sampling two primes, and then multiplying them together. – Geoffroy Couteau Mar 19 '20 at 12:59
• 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. – Kristian Francisco Milla Niels Mar 19 '20 at 13:21
• @KristianFranciscoMillaNiels see this other question – SEJPM Mar 19 '20 at 13:35
• @KristianFranciscoMillaNiels Also see the GCD Them ALL – kelalaka Mar 19 '20 at 14:17

• @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$. – fgrieu Apr 19 '20 at 12:20