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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.