Thumbnail
Access Restriction
Open

Author Rao, T. R. N. ♦ Yang, Chung-Huang
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Modular Arithmetic ♦ Public-key Cryptography ♦ Ancient India ♦ Diophantine Equation ♦ Compound Modulus ♦ Chinese Remainder Theorem ♦ Aryabhata Remainder Theorem ♦ Extended Euclidean Algorithm ♦ Indeterminate Equation ♦ Modular Inverse Operation ♦ Iterative Algorithm ♦ Mod Mi Xi ♦ Modulus Mi ♦ Modular Reduction ♦ Residue Number System ♦ Complexity Comparable ♦ Modular Inverse ♦ Aryabhatiya Algorithm
Abstract 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article