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?


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.

| improve this answer | |
  • $\begingroup$ 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). $\endgroup$ – fgrieu Dec 23 '13 at 12:24
  • 1
    $\begingroup$ @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...) $\endgroup$ – Reid Dec 23 '13 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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