Maurer法をベースとした確定的素数判定によるSafe Prime生成法とその高速化

スポンサーリンク

概要

論文の詳細を見る
暗号分野においては、pを素数としたとき、2p+1という形の素数が、しばしば用いられる。この形の素数はSafe Primeと呼ばれ、Diffie-Hellman鍵交換を始めとして、多くの暗号プロトコルで用いられている。このSafe Primeの高速生成法としては、これまでMiller-Rabin法をベースとする方法があった。しかしながら確率的素数判定法であるため、僅かではあるがSafe Primeでないものを生成する可能性があった。本稿では確定的素数判定であるMauer法をベースに用いたSafe Primeの効率的な生成法を複数取り上げ、それらの理論的な検討と実験による検証を行う。結論としてMauer法を用いた最も効率の良いSafe Prime生成法を1つ導き出した。また確率的素数判定法を用いた生成法に比べても同等の速度が実現できるという結果を得た。
一般社団法人情報処理学会の論文
2006-07-20

著者

関連論文

スポンサーリンク