Modular Arithmetic: From Ancient India to Public-Key Cryptography

Abstract. We begin with an algorithm from Aryabhatiya, for solving the indeterminate equation a·x + c = b·y of degree one (also known as Diophantine equation) and its extension to solve the system of two residues X mod mi = Xi (for i =1, 2). This contribution known as 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 is stated as Aryabhata Remainder Theorem (ART) and an iterative algorithm is given to solve for t moduli mi (i=1, 2,…, t). The ART, which has much in common with Extended Euclidean Algorithm (EEA), Chinese Remainder Theorem (CRT) and Garner’s algorithm (GA), is shown to have a complexity comparable or better than CRT and GA. Key words: Diophantine equation, Aryabhata, systems of congruences, modular arithmetic, residue number system, modular inverse