Miller-Rabinの確率的素数判定法の試行回数に関する予想
スポンサーリンク
概要
- 論文の詳細を見る
Miller-Rabinの確率的素数判定法(MR法)は、公開鍵暗号で必要となる10進で300桁程度の大きな素数を見付けるための素数判定法として良く用いられる。MR法では、大きな奇数nが素数であるか合成数であるかの判定を、ランダムに選んだb(l<b<n-1)について、(b,n)=lかつnが基底bに関して強擬素数(strong pseudoprime)である(これを「nはb-spspである」と書く)か否かを調べる。nがb-spspでないb(このようなbを「n(が合成数であること)のwitness(証拠)」と呼ぶ)が見付かれば、nは合成数である。ランダムに選んだk個の相異なるどのbについてもnがb-spspであれば、nが合成数である確率は高々4^-kである。本稿ではMR法の試行回数に関する次の予想を提出する。「kをk≧log n/log 4≒1.7 log nとなる最小の整数とすれば、nのwitnessは2,3,5,…の順に小さい方から並べたk個の素数の集合の中に見付かる。このようなk個の素数bについてnがb-spspであれば、nは素数である。」.
- 2002-11-08
著者
関連論文
- 有限体における楕円曲線上の有理点の乱数性
- SANE2000-42 ローカルエリアDGPSの補正データ推定の検討
- ロジスティック写像による擬似乱数生成器の乱数種への全数探索攻撃について
- ロジスティック写像による擬似乱数生成器の乱数種への全数探索攻撃について
- 暗号システムでの使用に適した乱数生成法(モバイル環境におけるPerson to Person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 暗号システムでの使用に適した乱数生成法(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- 暗号システムでの使用に適した乱数生成法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 暗号システムでの使用に適した乱数生成法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- Gold系列発生器
- 最適な周期相関値をもつ擬似乱数系列のクラス
- 九州工業大学情報工学部における「日本語表現技法」の授業及びこの授業に関する学生アンケートについて
- GF(3)上のm-系列の相互相関における Dobbertin の予想に関する考察
- 2元Gold系列から得られた良い相関特性をもつ4元系列セット
- 2元Gold-like系列をModifiedして得られた4元系列セットの相関分布
- 情報セキュリティにおける線形複雑度の役割
- Horster等の認証つき暗号を用いた署名の一人歩き防止プロトコル
- 周期2^nの2元周期系列 k-Error Linear Complexityの計算
- 相補系列の周期系列としての LC Profile と相関特性
- 同期P^n(P:素数)のP元周期系列のLinear Complexityの値の分布
- 系列のLinear Complexityの拡張とその応用(数理モデルの組合せ論的構造)
- On the Linear Complexity of Periodic Sequences Obtained from an M-Sequence(Combinatorial Structure in Mathematical Models)
- 巡回符号における定義集合と重み分布の関係に関する考察
- 系列の線形複雑度に関連する話題 (第22回情報理論とその応用シンポジウム)
- Miller-Rabinの確率的素数判定法の試行回数に関する予想
- Miller-Rabinの確率的素数判定法の試行回数に関する予想
- 周期p^n(p:素数)のp元周期系列のLinear Complexityの高速計算法
- Some Properties of Sequences over Integer Residue Rings Modulo q,q=pm and p a Prime
- 高次の座を用いた代数幾何符号の復号法に関する考察(その2)
- DESの安全性を高める簡単な方法
- DESの安全性を高める簡単な方法
- 系列の線形複雑度に関連する話題
- 系列のLinear Compexity(離散数理モデルにおける最適組合せ構造)