Kaihara, Marcelo E.Takagi, Naofumi2010-11-302010-11-302010-11-30200810.1109/TC.2007.70793https://infoscience.epfl.ch/handle/20.500.14299/61672WOS:000251686300002This paper proposes a new modular multiplication method that uses Montgomery residues defined by a modulus M and a Montgomery radix R whose value is less than the modulus M. This condition enables the operand multiplier to be split into two parts that can be processed separately in parallel-increasing the calculation speed. The upper part of the split multiplier can be processed by calculating a product modulo M of the multiplicand and this part of the split multiplier. The lower part of the split multiplier can be processed by calculating a product modulo M of the multiplicand, this part of the split multiplier, and the inverse of a constant R. Two different implementations based on this method are proposed: One uses a classical modular multiplier and a Montgomery multiplier and the other generates partial products for each part of the split multiplier separately, which are added and accumulated in a single pipelined unit. A radix-4 version of a multiplier based on a radix-4 classical modular multiplier and a radix-4 Montgomery multiplier has been designed and simulated. The proposed method is also suitable for software implementation in a multiprocessor environment.computer arithmetichardware algorithmmodular multiplicationMontgomery multiplicationComputer AlgorithmHardware Algorithmtext::journal::journal article::research article