A VLSI Modulo m Multiplier

In this paper, a new method to compute the exact digits of the modulo m product of integers is proposed and a modulo m multiply structure is defined. Such a structure can be implemented by means of few fast VLSI binary multipliers and a response time of about 150-200 ns to perform modular multiplications with moduli up to 32767 can be reached. A comparison to ROM-based structures is also provided. Finally, the modular multiplier has been evaluated asymptotically, according to the VLSI complexity theory, and it turned out to be an optimal design. This structure can be used to implement a residue multiplier in arithmetic structures using residue number systems (RNS), whenever such structures are interesting, because of their modularity and easy feasibility as VLSI components. The complexity of this residue multiplier has been evaluated and lower complexity figures than ROM-based multiply structures have been obtained, under several hypotheses on RNS parameters. © 1991 IEEE