ブロック分割を用いた素因数分解アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
今日の暗号システムの安全性は,素因数分解問題の難解さの仮定の下に保証されている.現在知られている効率のよい素因数分解アルゴリズムには,複数多項式二次ふるい法・数体ふるい法などがあるが,これらの方法は,ふるいにかける際のメモリ容量制限から,キャッシュミスなどによる実行速度の低下が大きい.そこで,WambachとWettigは二段化したブロック分割アルゴリズムを用い,ふるいデータのキャッシュミスを減らし複数多項式二次ふるい法の実行速度を2倍以上にすることに成功した.本論文では,ふるいデータのみならずキャッシュ上にある素数の効率的利用を図り,より速い二段ブロック分割アルゴリズムを構成しさらに二次キャッシュまでの効率的利用を図った三段ブロック分割アルゴリズムにより,100桁以上の合成数に対しWambachとWettigのアルゴリズムからさらに30〜40%の速度向上を得た.
- 一般社団法人情報処理学会の論文
- 1997-05-16