A hardware algorithm for modular division based on the extended euclidean algorithm

被引：0

作者：

Takagi, N

机构：

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 1996年 / E79D卷 / 11期

关键词：

Euclidean algorithm; hardware algorithm; modular arithmetic; modular division; redundant representation;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 propa- gation. 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.

引用

页码：1518 / 1522

页数：5

共 6 条

[1] A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS
ELGAMAL, T
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) : 469 - 472
[2] Knuth D.E., 1969, ART COMPUTER PROGRAM, V2, DOI 10.2307/2283757
[3] Parikh S. N., 1991, Proceedings. 10th IEEE Symposium on Computer Arithmetic (Cat. No.91CH3015-5), P220, DOI 10.1109/ARITH.1991.145563
[4] TAKAGI N, 1985, IEEE T COMPUT, V34, P789, DOI 10.1109/TC.1985.1676634
[5] TAKAGI N, 1993, IEICE T INF SYST, VE76D, P863
[6] MODULAR MULTIPLICATION HARDWARE ALGORITHMS WITH A REDUNDANT REPRESENTATION AND THEIR APPLICATION TO RSA CRYPTOSYSTEM
TAKAGI, N
YAJIMA, S
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (07) : 887 - 891

← 1 →