A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm(VLSI Design Technology and CAD)
スポンサーリンク
概要
- 論文の詳細を見る
A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We employ our newly proposed computation method that consists of processing the multiplier from the most significant digit first to calculate Montgomery multiplication. Finally, the ordinary modular multiplication is based on shift-and-add multiplication. Each of these three operations is carried out through the iteration of simple operations such as shifts and additions/subtractions. To avoid carry propagation in all additions and subtractions, the radix-2 signed-digit representation is employed. A modular multiplier/divider based on the algorithm has a linear array structure with a bit-slice feature and carries out n-bit modular multiplication/division in O(n) clock cycles, where the length of the clock cycle is constant and independent of n. This multiplier/divider can be implemented using a hardware amount only slightly larger than that of the modular divider.
- 一般社団法人電子情報通信学会の論文
- 2005-12-01
著者
-
Takagi Naofumi
Nagoya Univ. Nagoya‐shi Jpn
-
Kaihara Marcelo
Department Of Information Engineering Nagoya University
-
Takagi Naofumi
Department Of Communications And Computer Engineering Kyoto University
関連論文
- A Method of Sequential Circuit Synthesis Using One-Hot Encoding for Single-Flux-Quantum Digital Circuits(Superconducting Electronics)
- Logic Synthesis Method for Dual-Rail RSFQ Digital Circuits Using Root-Shared Binary Decision Diagrams(VLSI Design Technology and CAD)
- Floating-Point Euclidean Norm Computing Circuit
- Digit-Recurrence Algorithm for Computing Reciprocal Square-Root(Regular Section)
- A Hardware Algorithm for Integer Division Using the SD2 Representation(VLSI Design Technology and CAD)
- A VLSI Architecture for Output Probability Computations of HMM-Based Recognition Systems with Store-Based Block Parallel Processing
- 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
- A Clock Scheduling Algorithm for High-Throughput RSFQ Digital Circuits
- Comparisons of Synchronous-Clocking SFQ Adders
- Pipelined Bipartite Modular Multiplication
- Pipelined Bipartite Modular Multiplication
- Hardware Algorithm for Computing Reciprocal of Euclidean Norm of a 3-D Vector(VLSI Design Technology and CAD)
- Pipelined Bipartite Modular Multiplication
- Pipelined Bipartite Modular Multiplication
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- Layout-Driven Skewed Clock Tree Synthesis for Superconducting SFQ Circuits
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- A Digit-Recurrence Algorithm for Cube Rooting
- A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm(VLSI Design Technology and CAD)
- A VLSI Architecture with Multiple Fast Store-Based Block Parallel Processing for Output Probability and Likelihood Score Computations in HMM-Based Isolated Word Recognition