# RSA with modulus product of many primes

I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with $p$ and $q$ large prime numbers. I guess the modulus $n=p_{1}p_{2}...p_{L}$ will be not a good idea, because one can use the Chinese Remainder Theorem to decrypt easily the message?

Can anybody explain how we deal with such moduli products of many primes?

• You can use multiple primes as long as they're large enough. It gives you less security for a given modulus size, but it can give you a better performance/security trade-off. – CodesInChaos Oct 25 '13 at 19:39
• – CodesInChaos Oct 25 '13 at 19:40

On the plus side, this may offer some performance improvement. The Chinese Remainder Theorem still applies (see for instance in section 5.1.2, the description accommodates more than two primes). For instance, if you have a 1536-bit modulus which is the product of three 512-bit primes, then the CRT replaces one 1536-bit exponentiation with three 512-bit exponentiations which are, individually, 27 times faster (assuming a classic cubic modular exponentiation algorithm), for a total speedup of 9, compared to the usual 4 with two factors. More generally, with $$k$$ factors, the expected CRT speedup is in about $$k^2$$.