Residue arithmetic in binary systems

A natural approach to the problem of performing mod m computations in a binary system is presented and a solution is suggested which is based upon a straightforward relation between the residues of a same integer X with respect to different moduli. The proposed solution proves fruitful in various applications, such as converting binary integers to residue notation and mod m addition or multiplication. Even if the most usual implementation approach for mod m processors is based on look-up tables, the use of a binary number system keeps its validity those situations, such as large-moduli residue arithmetic or conversion processes, where a memory approach is not viable. Moreover, VLSI area-time complexity aspects are considered for the presented applications and constructive proofs are given showing that the complexities of mod m and binary addition/multiplication structures coincide.