複数多項式汎用数体ふるい法の検証
スポンサーリンク
概要
- 論文の詳細を見る
今日の暗号システムの安全性は、素因数分解問題の難解さの仮定のもとに保証されている。現在知られている素因数分解アルゴリズムの中で、合成数とその因数が大きな場合には、汎用数体ふるい法(GNFS)が最も高速であることが知られている。GNFSの高速化としては、Pollardによるlattice sieveや、Montgomeryによる複数多項式汎用数体ふるい法(MPGNFS)などがある。本研究では、これらの高速化を含むGNFSのふるいの部分を実装し、その性能を検証する。その結果今回の実験では2つの多項式を使ったlattice sieveが最も高速であることが分った。本論文ではまた、多項式を選択する際の尺度を幾つか与え、その有効性を比較する。
- 一般社団法人情報処理学会の論文
- 1998-05-20