| 講演抄録／キーワード |
| 講演名 |
2006-07-20 14:15
Maurer法をベースとした確定的素数判定によるSafe Prime生成法とその高速化
○熊給英洋・丹羽朗人（東芝ソリューション） |
| 抄録 |
（和） |
暗号分野においては、pを素数としたとき、2p+1という形の素数が、しばしば用いられる。この形の素数はSafe Primeと呼ばれ、Diffie-Hellman鍵交換を始めとして、多くの暗号プロトコルで用いられている。このSafe Primeの高速生成法としては、これまでMiller-Rabin法をベースとする方法があった。しかしながら確率的素数判定法であるため、僅かではあるがSafe Primeでないものを生成する可能性があった。本稿では確定的素数判定であるMaurer法をベースに用いたSafe Primeの効率的な生成法を複数取り上げ、それらの理論的な検討と実験による検証を行う。結論としてMaurer法を用いた最も効率の良いSafe Prime生成法を１つ導き出した。また確率的素数判定法を用いた生成法に比べても同等の速度が実現できるという結果を得た。 |
| （英） |
A prime number of the form 2p + 1, where p is also a prime is often used in cryptography.The prime of this form is called "Safe Prime".Safe prime is used by a lot of cryptographic protocols including Diffie-Hellman key exchange.To generate the Safe Prime, some methods based on the Miller-Rabin method are known, however these methods can generate prime numbers probabilistically.We analyzed several deterministic methods based on the Maurer Method, and the result was verified experimentally.We deduced the most effective method, whose efficiency was almost same as the probabilistic methods. |
| キーワード |
（和） |
Safe Prime / Sophie Germain Prime / Maurer法 / Euler-Lagrangeの定理 / Miller-Rabin法 / 素数生成法 / / |
| （英） |
Safe Prime / Sophie Germain Prime / Maurer Method / Euler-Lagrange theorem / Miller-Rabin method / Prime Generation / / |
| 文献情報 |
信学技報, vol. 106, no. 175, ISEC2006-23, pp. 103-110, 2006年7月. |
| 資料番号 |
ISEC2006-23 |
| 発行日 |
2006-07-13 (ISEC, SITE) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
|