A Modular Inversion Hardware Algorithm with a Redundant Binary Representation

Naofumi TAKAGI

A Modular Inversion Hardware Algorithm with a Redundant Binary Representation

Naofumi TAKAGI

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E76-D No.8 pp.863-869

Publication Date: 1993/08/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Hardware and Design

Cite this

Copy

Naofumi TAKAGI, "A Modular Inversion Hardware Algorithm with a Redundant Binary Representation" in IEICE TRANSACTIONS on Information, vol. E76-D, no. 8, pp. 863-869, August 1993, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e76-d_8_863/_p

Copy

@ARTICLE{e76-d_8_863,
author={Naofumi TAKAGI, },
journal={IEICE TRANSACTIONS on Information},
title={A Modular Inversion Hardware Algorithm with a Redundant Binary Representation},
year={1993},
volume={E76-D},
number={8},
pages={863-869},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - A Modular Inversion Hardware Algorithm with a Redundant Binary Representation
T2 - IEICE TRANSACTIONS on Information
SP - 863
EP - 869
AU - Naofumi TAKAGI
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1993
AB - 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.
ER -