A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm

Marcelo E. KAIHARA  Naofumi TAKAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A    No.12    pp.3610-3617
Publication Date: 2005/12/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.12.3610
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
modular arithmetic,  modular multiplication,  modular division,  Montgomery multiplication,  extended Euclidean algorithm,  hardware algorithm,  

Full Text: PDF>>
Buy this Article

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.