Miller-Rabinの確率的素数判定法の試行回数に関する予想

摘要

Miller-Rabinの確率的素数判定法（MR法）は、公開鍵暗号で必要となる10進で300桁程度の大きな素数を見付けるための素数判定法として良く用いられる。 MR法では、大きな奇数nが素数であるか合成数であるかの判定を、ランダムに選んだb (1＜b＜n－1)について、(b, n)＝1かつnが基底bに関して強擬素数(strong pseudoprime) である（これを「nはb-spspである」と書く）か否かを調べる。 nがb-spspでないb（このようなbを「n（が合成数であること）のwitness（証拠）」と呼ぶ）が見付かれば、nは合成数である。 ランダムに選んだk個の相異なるどのbについてもnがb-spspであれば、nが合成数である確率は高々4{sup}(-k)である。 本稿ではMR法の試行回数に関する次の予想を提出する。 「kをk≧logn/log4≒1.7lognとなる最小の整数とすれば、nのwitnessは2,3,5,…の順に小さい方から並べたk個の素数の集合の中に見付かる。 このようなk個の素数bについてnがb-spspであれば、nは素数である。 」．