Abstract
Public-key crypto-algorithms are widely employed for authentication, signatures, secret-key generation and access control. The new range of public-key sizes for RSA and DSA has gone up to 1024 bits and beyond. The elliptic-curve key range is from 162 bits to 256 bits. Many varied software and hardware algorithms are being developed for implementation for smart-card crypto-coprocessors and for public-key infrastructure. We begin with an algorithm from Aryabhatiya for solving the indeterminate equation a · x + c = b · y of degree one (also known as the Diophantine equation) and its extension to solve the system of two residues X mod mi = Xi (for i = 1,2). This contribution known as the Aryabhatiya algorithm (AA) is very profound in the sense that the problem of two congruences was solved with just one modular inverse operation and a modular reduction to a smaller modulus than the compound modulus. We extend AA to any set of t residues, and this is stated as the Aryabhata remainder theorem (ART). An iterative algorithm is also given to solve for t moduli mi (i = 1, 2,... , t). The ART, which has much in common with the extended Euclidean algorithm (EEA), Chinese remainder theorem (CRT) and Garner's algorithm (GA), is shown to have a complexity comparable to or better than that of the CRT and GA.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Rao, T., Yang, CH. Aryabhata Remainder Theorem: Relevance to Public-Key Crypto-Algorithms. Circuits Syst Signal Process 25, 1–15 (2006). https://doi.org/10.1007/s00034-005-1123-6
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s00034-005-1123-6