A Hardware Algorithm for Modular Division Based on the Extended Euclidean Algorithm
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 1996-11-25
著者
関連論文
- Floating-Point Euclidean Norm Computing Circuit
- Digit-Recurrence Algorithm for Computing Reciprocal Square-Root(Regular Section)
- Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees (Special Section on Discrete Mathematics and Its Applications)
- Proposal of a Desk-Side Supercomputer with Reconfigurable Data-Paths Using Rapid Single-Flux-Quantum Circuits
- 100GHz Demonstrations Based on the Single-Flux-Quantum Cell Library for the 10kA/cm^2 Nb Multi-Layer Process
- Automated Passive-Transmission-Line Routing Tool for Single-Flux-Quantum Circuits Based on A^* Algorithm
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- A Multiple-Precision Modular Multiplication Algorithm with Triangle Additions
- A Hardware Algorithm for Modular Division Based on the Extended Euclidean Algorithm
- A Digit-Recurrence Algorithm for Cube Rooting