High-Radix Design of a Scalable Montgomery Modular Multiplier With Low Latency
- 19 January 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 71 (2) , 436-449
Abstract
The proposed herein is a scalable high-radix (i.e., $2^m$ ) Montgomery Modular (MM) Multiplication circuit replacing the integer multiplications in each iteration of the Montgomery MM algorithm (related to the product of $m$ bits of the multiplier and the multiplicand) with carry-save compressions and completely eliminating costly multiplications. Furthermore, the proposed Montgomery MM decomposes the multiplicand itself using a radix of $2^w$ with $w\geq 2m$ , thereby achieving a scalable design, which can deliver an issue latency of one cycle and a cycle (count) latency of $O(N^2/(wmp))$ where $p$ denotes the number of available processing elements, each of which is designed to complete the above iteration by computing in part the product of $w$ bits of the multiplicand and $m$ bits of the multiplier. The area complexity of the proposed Montgomery MM is $O(wmp)$ , and thus, the Area-Latency-Product complexity is $O(N^{2})$ .
Keywords
This publication has 28 references indexed in Scilit:
- Fully homomorphic encryption using ideal lattices2009
- An efficient CSA architecture for montgomery modular multiplicationMicroprocessors and Microsystems, 2007
- Parallelized radix-4 scalable montgomery multipliers2007
- A scalable architecture for modular multiplication based on montgomery's algorithmIEEE Transactions on Computers, 2003
- Montgomery Exponentiation with no Final Subtractions: Improved Results2000
- Montgomery’s Multiplication Technique: How to Make It Smaller and Faster1999
- Elliptic Curve CryptosystemsMathematics of Computation, 1987
- Modular multiplication without trial divisionMathematics of Computation, 1985
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- A SIGNED BINARY MULTIPLICATION TECHNIQUEQuarterly Journal of Mechanics and Applied Mathematics, 1951