Advertisement
Published in:
2007 | OriginalPaper | Chapter
Dual-Residue Montgomery Multiplication
Authors : Anding Wang, Yier Jin, Shiju Li
Published in: Network and Parallel Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The paper introduces a new approach based on dual residue system to compute Montgomery multiplication. The novelty of this proposal is that we import an extra Montgomery residue system with new transformation constant beside the normal one. In this way, one of the multiplicand can be divided into two parts and both higher and lower parts are calculated in parallel to speed up computation. Then two implementations in hardware are proposed for the algorithm. In parallel architecture, the proposed algorithm can perform nearly twice speedup compared to normal Montgomery method. And in pipeline architecture, the computation speed can be even faster. Besides speeding up calculation the extra merit of our proposal is that the multiplier can partial replace Montgomery multiplier used nowadays without any changes on top architecture.