A division algorithm for residue numbers

摘要

In the residue number system, modular multiplication, modular addition, and modular subtraction are closure operations. However, modular division is also important for applying the residue number system. Inspired by Gamberger’s work, we create a division operation to be used in residue number system. In Gamberger’s scheme, the transformation from residues to a binary integer is required for keeping the remainder. To eliminate the overhead in transformation, our scheme uses only the residues so that the computing efficiency can be improved. Besides, we also provide an efficient way to find a multiplicative inverse.