# What parts of number theory does the RSA algorithm use?

It is said that the RSA algorithm uses number theory. What parts of number theory does it use?
I know it uses modular arithmetic and Euler's totient theorem and function. Is that all?

## 1 Answer

Other than Euler's phi function and modular arithmetic, RSA also make use of Fermat’s Little Theorem (number theory) and depends on the assumption that given the product of two large primes, one cannot factor the product in a reasonable time to solve the RSA problem.

i.e. even if we know e we cannot figure out d unless we know phi(n) which requires factoring n. While there is no proof that factorization is computationally difficult, no efficient solution has been found yet.

• In fact, RSA as practiced (that is, PKCS#1) does not even use Euler's phi function for $d\equiv e^{-1}\pmod {\phi(N)}$; but rather uses the (less frightening) Least Common Multiple: $d\equiv e^{-1}\pmod {\operatorname{LCM}(p-1,q-1)}$, because that's the necessary and sufficient condition for a working $d$ (when all the factors of $N$ are distinct). – fgrieu Dec 23 '13 at 12:24
• @fgrieu: Well, I don't know if the Carmichael function is really all that less-frightening! (At least, not if you approach the problem from a theory-heavy point of view instead of just ignoring the whole issue...) – Reid Dec 23 '13 at 16:17