| Presentation | 2004/5/20 A Multiplier/Divider for Modular Arithmetic Based on the Extended Euclidean Algorithm Marcelo E. KAIHARA, Naofumi TAKAGI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We propose a multiplier/divider for modular arithmetic suitable for VLSI realization. It is based on our newly proposed combined algorithm for modular multiplication and division. It performs modular division, Montgomery's modular multiplication and ordinary modular multiplication. Modular division is based on the extended Euclidean algorithm. Montgomery's modular multiplication is based on our newly proposed method consisting of processing the multiplier from the most significant digit first. The ordinary modular multiplication is based on conventional doubling and adding procedures. The three operations are carried out through iteration of simple operations such as shifts and addition/subtractions. The radix-2 signed-digit representation is employed so that all additions and subtractions are performed without carry propagation. The multiplier/divider for modular arithmetic 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. The multiplier/divider can be implemented with much smaller hardware than the necessary to implement ordinary modular multiplier, Montgomery's modular multiplier and divider separately. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | modular arithmetic / modular multiplication / modular division / Montgomery's algorithm / extended Euclidean algorithm / hardware algorithm / VLSI algorithm |
| Paper # | VLD2004-1 |
| Date of Issue |
| Conference Information | |
| Committee | VLD |
|---|---|
| Conference Date | 2004/5/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | VLSI Design Technologies (VLD) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Multiplier/Divider for Modular Arithmetic Based on the Extended Euclidean Algorithm |
| Sub Title (in English) | |
| Keyword(1) | modular arithmetic |
| Keyword(2) | modular multiplication |
| Keyword(3) | modular division |
| Keyword(4) | Montgomery's algorithm |
| Keyword(5) | extended Euclidean algorithm |
| Keyword(6) | hardware algorithm |
| Keyword(7) | VLSI algorithm |
| 1st Author's Name | Marcelo E. KAIHARA |
| 1st Author's Affiliation | Department of Information Engineering, Nagoya University() |
| 2nd Author's Name | Naofumi TAKAGI |
| 2nd Author's Affiliation | Department of Information Engineering, Nagoya University |
| Date | 2004/5/20 |
| Paper # | VLD2004-1 |
| Volume (vol) | vol.104 |
| Number (no) | 78 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |