View in EDS

High-Radix Design of a Scalable Montgomery Modular Multiplier With Low Latency.

Saved in:
Bibliographic Details
Title: High-Radix Design of a Scalable Montgomery Modular Multiplier With Low Latency.
Authors: Zhang, Bo1 (AUTHOR) zhan254@usc.edu, Cheng, Zeming1 (AUTHOR) zemingch@usc.edu, Pedram, Massoud1 (AUTHOR) pedram@usc.edu
Source: IEEE Transactions on Computers. Feb2022, Vol. 71 Issue 2, p436-449. 14p.
Subjects: Data compression, Elliptic curve cryptography, Multiplication
Abstract: The proposed herein is a scalable high-radix (i.e., $2^m$ 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$ 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$ 2 w with $w\geq 2m$ w ≥ 2 m , thereby achieving a scalable design, which can deliver an issue latency of one cycle and a cycle (count) latency of $O(N^2/(wmp))$ O (N 2 / (w m p)) where $p$ 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$ w bits of the multiplicand and $m$ m bits of the multiplier. The area complexity of the proposed Montgomery MM is $O(wmp)$ O (w m p) , and thus, the Area-Latency-Product complexity is $O(N^{2})$ O (N 2) . [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Computers is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:The proposed herein is a scalable high-radix (i.e., $2^m$ 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$ 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$ 2 w with $w\geq 2m$ w ≥ 2 m , thereby achieving a scalable design, which can deliver an issue latency of one cycle and a cycle (count) latency of $O(N^2/(wmp))$ O (N 2 / (w m p)) where $p$ 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$ w bits of the multiplicand and $m$ m bits of the multiplier. The area complexity of the proposed Montgomery MM is $O(wmp)$ O (w m p) , and thus, the Area-Latency-Product complexity is $O(N^{2})$ O (N 2) . [ABSTRACT FROM AUTHOR]
ISSN:00189340
DOI:10.1109/TC.2021.3052999