IEICE TRANSACTIONS on Fundamentals
A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm
Summary :
A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We employ our newly proposed computation method that consists of processing the multiplier from the most significant digit first to calculate Montgomery multiplication. Finally, the ordinary modular multiplication is based on shift-and-add multiplication. Each of these three operations is carried out through the iteration of simple operations such as shifts and additions/subtractions. To avoid carry propagation in all additions and subtractions, the radix-2 signed-digit representation is employed. A modular multiplier/divider based on the algorithm has a linear array structure with a bit-slice feature and carries out n-bit modular multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. This multiplier/divider can be implemented using a hardware amount only slightly larger than that of the modular divider.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.12 pp.3610-3617
- Publication Date
- 2005/12/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.12.3610
- Type of Manuscript
- PAPER
- Category
- VLSI Design Technology and CAD
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Marcelo E. KAIHARA, Naofumi TAKAGI, "A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 12, pp. 3610-3617, December 2005, doi: 10.1093/ietfec/e88-a.12.3610.
Abstract: A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We employ our newly proposed computation method that consists of processing the multiplier from the most significant digit first to calculate Montgomery multiplication. Finally, the ordinary modular multiplication is based on shift-and-add multiplication. Each of these three operations is carried out through the iteration of simple operations such as shifts and additions/subtractions. To avoid carry propagation in all additions and subtractions, the radix-2 signed-digit representation is employed. A modular multiplier/divider based on the algorithm has a linear array structure with a bit-slice feature and carries out n-bit modular multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. This multiplier/divider can be implemented using a hardware amount only slightly larger than that of the modular divider.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.12.3610/_p
Copy
@ARTICLE{e88-a_12_3610,
author={Marcelo E. KAIHARA, Naofumi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm},
year={2005},
volume={E88-A},
number={12},
pages={3610-3617},
abstract={A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We employ our newly proposed computation method that consists of processing the multiplier from the most significant digit first to calculate Montgomery multiplication. Finally, the ordinary modular multiplication is based on shift-and-add multiplication. Each of these three operations is carried out through the iteration of simple operations such as shifts and additions/subtractions. To avoid carry propagation in all additions and subtractions, the radix-2 signed-digit representation is employed. A modular multiplier/divider based on the algorithm has a linear array structure with a bit-slice feature and carries out n-bit modular multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. This multiplier/divider can be implemented using a hardware amount only slightly larger than that of the modular divider.},
keywords={},
doi={10.1093/ietfec/e88-a.12.3610},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3610
EP - 3617
AU - Marcelo E. KAIHARA
AU - Naofumi TAKAGI
PY - 2005
DO - 10.1093/ietfec/e88-a.12.3610
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2005
AB - A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We employ our newly proposed computation method that consists of processing the multiplier from the most significant digit first to calculate Montgomery multiplication. Finally, the ordinary modular multiplication is based on shift-and-add multiplication. Each of these three operations is carried out through the iteration of simple operations such as shifts and additions/subtractions. To avoid carry propagation in all additions and subtractions, the radix-2 signed-digit representation is employed. A modular multiplier/divider based on the algorithm has a linear array structure with a bit-slice feature and carries out n-bit modular multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. This multiplier/divider can be implemented using a hardware amount only slightly larger than that of the modular divider.
ER -
English
