Mathematical Foundations of RSA Encryption and Its Computational Implications

RSA is the most widely deployed public-key cryptosystem for key establishment and digital signatures. Its appeal comes from an unusually clean mathematical structure: modular exponentiation in the ring Z_N combined with Euler’s theorem (or, more precisely, the Chinese Remainder Theorem over prime factors of N). This paper reviews the number-theoretic foundations that make RSA correct, then connects those foundations to computational realities: the asymptotic and practical costs of key generation and exponentiation, the security reductions and pitfalls introduced by padding and protocol composition, and the algorithmic landscape of integer factorization that governs recommended key sizes. We emphasize the gap between the mathematical idealization (a trapdoor permutation) and real implementations that must confront randomness failures, side channels, and evolving computational capabilities including quantum algorithms. The goal is to provide a unified view of RSA as both a mathematical object and an engineered system.