The VLSI residue multiplication and its implication in the direct and reverse positional-to-residue conversion

Computing structures based on Residue Number Sistems are very interesting because addition and multiplication are fast and modular and are well suited for VLSI implementation. In this paper the problem of multiplying two integers in residue representation is faced with and a new modulo m multiplier is defined. Such a multiplier can be integrated on a single chip with present VLSI technology and exhibits, for example, an expected response time of about 150 nseconds to multiply integers ranging up to 10?12 using five 8-bit moduli. It allows any choice of moduli values and has considerably low complexity figures, if compared with ROM-based structures, which are generally considered the most suited for RNS-based systems. Finally, new direct and reverse converters between binary positional representation and residue representation, exploiting the multiplier structure defined, are presented. They are the best solutions known under a wide range of hypotheses about RNS's.