# RSA How to find the private key to a given public key when n doesn't consist of two primes?

I have the homework to find to the public key (120, 3) the private key. I guess 120 is n and 3 will be e. So that $$\lfloor\sqrt{120}\rfloor=10$$ I can't find a matching prime number. So it gets more complicated. I also know $$\phi(n)=(p-1)(q-1)$$ and $$3\cdot d\equiv 1\mod (p-1)(q-1)$$ But here I stuck, could somebody help me from this point on?

• $120=2^3\cdot 3\cdot 5$ so this is indeed multi-prime RSA. – SEJPM Sep 22 '18 at 15:56
• so do I need to compute $\phi(n)=(2-1)^3\cdot(3-1)\cdot(5-1)$ and then $3\cdot d\equiv 1\mod 8$ with $d = e = 3$? – baxbear Sep 22 '18 at 15:59
• does multi-prime RSA make any sense in practical use? – baxbear Sep 22 '18 at 16:01
• Multi prime RSA can be usefull as long as you keep all primes large. I read a while ago a proposal to use multiprime RSA for post quantom encryption relying on a large polynomial advantage for honest user over attacker. I liked not requiring expononetial advantage as usuall. – Meir Maor Sep 22 '18 at 20:21

I also know $$\phi(n)=(p-1)(q-1)$$

This actually only holds if $$n=pq$$ and if $$p$$ and $$q$$ are both primes.

When $$n$$ doesn't factor as nicely you'll need the more general definition of $$\phi(n)$$ which can be computed from the following three axioms (given the prime factorization of $$n$$):

• If $$\gcd(n,m)=1$$ for any $$n,m$$ then $$\phi(n\cdot m)=\phi(n)\phi(m)$$
• If $$p$$ is prime and $$k\geq 1$$ then $$\phi(p^k)=p^{k-1}(p-1)$$

So in your case $$\phi(120)=\phi(2^3\cdot 3\cdot 5)=\phi(2^3)\phi(3)\phi(5)=(2^2\cdot1)\cdot2\cdot4=32$$

does multi-prime RSA make any sense in practical use?

Yes, using more than two primes can make sense if you use the chinese remainder theorem (CRT) which yields a speed-up of $$k^2/4$$ for $$k$$ primes compared to using only $$k=2$$. See fgrieu's excellent answer for a discussion of why one wants that and what one has to look out for when actually deploying multi-prime RSA and the table in DW's answer to the same question for an overview of how many primes to use for each modulus size.