A Modular Inversion Hardware Algorithm with a Redundant Binary Representation

Naofumi TAKAGI  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.8   pp.863-869
Publication Date: 1993/08/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Hardware and Design
computer arithmetic,  computer cryptograph,  greatest common divisor (GCD),  hardware algorithm,  modular arithmetic,  

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

A hardware algorithm for modular inversion is proposed. It is based on the extended Euclidean algorithm. All intermediate results are represented in a redundant binary representation with a digit set {0, 1,1}. All addition/subtractions are performed without carry propagation. A modular inversion is carried out in O (n) clock cycles where n is the word length of the modulus. The length of each clock cycle is constant independent of n. A modular inverter based on the algorithm has a regular cellular array structure with a bit slice feature and is very suitable for VLSI implementation. Its amount of hardware is proportional to n.