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

Naofumi TAKAGI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.11   pp.1518-1522
Publication Date: 1996/11/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Hardware and Design
Keyword: 
Euclidean algorithm,  hardware algorithm,  modular arithmetic,  modular division,  redundant representation,  

Full Text: PDF(404.8KB)
>>Buy this Article

Summary: 
A hardware algorithm for modular division is proposed. It is based on the extended Euclidean algorithm (EEA). The procedure for finding the multiplicative inverse in EEA is modified so that it calculates the quotient. Modular division is carried out through iteration of simple operations, such as shifts and additions. A redundant binary representation is employed so that additions are performed without carry propagation. An n-bit modular division is carried out in O(n) clock cycles. The length of each clock cycle is constant independent of n. A modular divider based on the algorithm has a bit-slice structure and is suitable for VLSI implementation.