| Presentation | 2019-01-30 Proposal of reduction method of calculations by using Leading Zero in the Extended Euclidean Algorithm Masaki Ogino, Yuki Tanaka, Shugang Wei, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The modular multiplication inverse is used to generate the secret key of the public key cryptosystem from the difficulty of analysis due to the discrete logarithm problem, and high speed computation method has been desired conventionally. The extended Euclidean algorithm is an algorithm to calculate the modular multiplication inverse at high speed. In this study, the division and multiplication of the extended Euclidean algorithm are computed by using a subtraction circuit and an addition circuit with a pipeline structure. To reduce the times of the subtractions and additions in the division and multiplication of the extended Euclidean algorithm, we introduce Leading Zero circuit into the controlling unit. By experiments with some numeral computations, it is shown that a high speed modular multiplication inverse can be achieved. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Modular multiplicative inverse / Extended euclidean algorithm / Leading zero |
| Paper # | VLD2018-73,CPSY2018-83,RECONF2018-47 |
| Date of Issue | 2019-01-23 (VLD, CPSY, RECONF) |
| Conference Information | |
| Committee | IPSJ-SLDM / RECONF / VLD / CPSY / IPSJ-ARC |
|---|---|
| Conference Date | 2019/1/30(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Raiosha, Hiyoshi Campus, Keio University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | FPGA Applications, etc. |
| Chair | Yutaka Tamiya(Fujitsu Lab.) / Masato Motomura(Hokkaido Univ.) / Noriyuki Minegishi(Mitsubishi Electric) / Koji Nakano(Hiroshima Univ.) / Koji Inoue(Kyushu Univ.) |
| Vice Chair | / Yuichiro Shibata(Nagasaki Univ.) / Kentaro Sano(RIKEN) / Nozomu Togawa(Waseda Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) |
| Secretary | (NEC) / Yuichiro Shibata(Kochi Univ. of Tech.) / Kentaro Sano(NTT) / Nozomu Togawa(Hiroshima City Univ.) / Hidetsugu Irie(e-trees.Japan) / Takashi Miyoshi(NTT) / (Univ. of Aizu) |
| Assistant | / Yuuki Kobayashi(NEC) / Hiroki Nakahara(Tokyo Inst. of Tech.) / / Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) |
| Paper Information | |
| Registration To | Special Interest Group on System and LSI Design Methodology / Technical Committee on Reconfigurable Systems / Technical Committee on VLSI Design Technologies / Technical Committee on Computer Systems / Special Interest Group on System Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Proposal of reduction method of calculations by using Leading Zero in the Extended Euclidean Algorithm |
| Sub Title (in English) | |
| Keyword(1) | Modular multiplicative inverse |
| Keyword(2) | Extended euclidean algorithm |
| Keyword(3) | Leading zero |
| 1st Author's Name | Masaki Ogino |
| 1st Author's Affiliation | Gunma University(Gunma Univ.) |
| 2nd Author's Name | Yuki Tanaka |
| 2nd Author's Affiliation | Gunma University(Gunma Univ.) |
| 3rd Author's Name | Shugang Wei |
| 3rd Author's Affiliation | Gunma University(Gunma Univ.) |
| Date | 2019-01-30 |
| Paper # | VLD2018-73,CPSY2018-83,RECONF2018-47 |
| Volume (vol) | vol.118 |
| Number (no) | VLD-430,CPSY-431,RECONF-432 |
| Page | pp.pp.7-12(VLD), pp.7-12(CPSY), pp.7-12(RECONF), |
| #Pages | 6 |
| Date of Issue | 2019-01-23 (VLD, CPSY, RECONF) |