Number Theoretic Foundations of Cryptography: From Congruence Theory to RSA - Atiq, Bahadur; Fakhri, Nooruddin; Wahdat, Zia (Journal of Advanced Computer Knowledge and Algorithms, 2026)
Number theory, particularly modular arithmetic and congruence theory, constitutes the mathematical backbone of modern cryptography. Foundational results such as Euler’s theorem, Fermat’s little theorem, and the Chinese Remainder Theorem (CRT) have long shaped secure communication by providing the theoretical infrastructure for computational techniques like modular exponentiation. Building on these classical insights, this paper explores the deep interplay between number-theoretic foundations and cryptographic applications, tracing their role from traditional public-key systems (RSA, ElGamal, and Diffie-Hellman) to cutting-edge post-quantum paradigms. We emphasize the centrality of congruences in enabling efficient modular exponentiation, ensuring the scalability and security of large-scale data transmission. Beyond classical protocols, the study critically examines security assumptions in light of emerging quantum threats, particularly Shor’s algorithm, which undermines conventional systems and necessitates the urgent development of resilient post-quantum methods. Recent advancements in lattice-based, code-based, and multivariate cryptography are reviewed, highlighting their mathematical underpinnings and practical readiness. Furthermore, a comparative analysis of congruence-based cryptosystems is presented, focusing on computational complexity, efficiency trade-offs, and real-world deployment in blockchain, digital signatures, and the Internet of Things (IoT). By bridging classical number theory with contemporary cryptographic challenges, this paper offers both theoretical insight and applied perspective, underscoring the enduring significance and evolving nature of congruence theory in safeguarding digital communication systems.