.png){kind=icon}
.png){kind=icon}
Return
Bipartite modular multiplication method
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2007.70793.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This 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.
Keywords:
computer arithmetic
hardware algorithm
modular multiplication
Montgomery multiplication
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K