Miller-Rabinテストでの誤判定確率の実験的計測値と理論的上界値との比較

スポンサーリンク

概要

論文の詳細を見る
Miller-Rabinテストにおける誤判定確率(強probable primeが強擬素数である確率)の理論上界を, ビット長100以上300以下のランダムに生成した奇数について計測した実験値と比較した.その結果, 理論での期待値により各ビット長で16個程度強擬素数が観測されるはずの強probable primeの個数について実際には強擬素数は全く観測されなかった.この結果を統計的に解析することにより, 300ビット以下での実際の誤判定確率は95%の信頼度で現状での最小の理論上界よりも1/4以下であろうという推測値を得た.
2005-07-14

著者

中島俊哉
(株)富士通研究所

関連論文

スポンサーリンク