一般数体篩法実装実験(6) : 格子篩
スポンサーリンク
概要
- 論文の詳細を見る
小さな因子を含まない数百ビット以上の合成数に対する素因数分解アルゴリズムとして,数体篩法が現在最も高速と考えられている.数体篩法のうち最も計算量を必要とするのは篩処理である.篩処理には素朴な方法であるline sieveがあり,現在でもよく使われているが,一般数体篩法で500ビット程度以上の分解を目指すとなるとlattice sieveは必須の技術である.しかしながらlattice sieveは複雑であり,細かい実装法については文献が少ない.本稿では,lattice sieveのアルゴリズムを詳細に記述する.
- 社団法人電子情報通信学会の論文
- 2004-09-10
著者
関連論文
- 数体篩法における篩領域,必要relation数と因子基底数について
- 一般数体篩法実装実験(5) : バケツ整列を利用した篩の高速化
- 一般数体篩法実装実験(5) : バケツ整列を利用した篩の高速化
- 一般数体篩法実装実験(4) : 線形代数(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(3) : Filtering(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(2) : ミニ素因数分解・ミニ素数判定(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(4) : 線形代数(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(3) : Filtering(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(2) : ミニ素因数分解・ミニ素数判定(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(4) : 線形代数(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(3) : Filtering(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(2) : ミニ素因数分解・ミニ素数判定(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 一般数体篩法実装実験(6) : 格子篩
- 素因数分解の現状について
- Chris K. Caldwell, SOJIN訳, 『素数大百科』
- 素数判定アルゴリズム ( 数論アルゴリズムとその応用)
- 多倍長ソフトを用いた計算機教育