素数ではなくて…… (2)
> 一点、質問をさせていただきたく思います。
> ミラーラビンの底には素数をとるのが良いのでしょうか？ 確率の評価に影響をあたえますか？
影響は大いにあると思います。
例えば2で確率的素数と判定されたら4や8でも（多分）確率的素数と判定されますが、確率が上がるわけではないですね。
同様に、2と3で確率的素数となれば6でも（多分）確率的素数と判定されると思います。
「多分」としているのは場合によるかも知れないからですが、影響する可能性があるのは間違いないですから、同じ素因数を持つ数は避けた方が良いかと思います。
> 同様に、2と3で確率的素数となれば6でも（多分）確率的素数と判定されると思います。
私はこれはなんとなく偽ではないかと思います。
反例はまだ見つけられていませんが。
> 2と3で確率的素数となれば6でも（多分）確率的素数
例えばnが素数でn-1=16m（mは奇数）だとすると、mod nで
(a^m,a^(2m),a^(4m),a^(8m),a^(16m))≡
(1,1,1,1,1),
(-1,1,1,1,1),
(A,-1,1,1,1),
(B,C,-1,1,1),
(D,E,F,-1,1)
(A,B,C,D,E,Fは-1,0,1以外の数)
のいずれかになるわけですが、
a=2で
(A,-1,1,1,1)
a=3で
(D,E,F,-1,1)
のようになったとすると、a=6では
(A*D,-E,F,-1,1) （A*Dも-EもFも-1,0,1以外）
のようになり、やはり確率的素数と判定されます。
問題は
底2で (A,B,C,-1,1)
底3で (D,E,F,-1,1)
のように同じタイミングで-1になった場合で、
このような場合はC*F≡-1になるとは限りませんので
底6で確率的素数と判定されるかどうかわかりません。
（これの反例があるのかどうかもわかりません。ありそうな気はしますが）
というわけで、少なくとも-1になるタイミングが異なる素因数の積を
底にした判定は確率の向上になりませんので、同じ素因数は避けた方がいい、
ということを言いたかったのです。
> 少なくとも-1になるタイミングが異なる素因数の積を底にした判定は確率の向上になりませんので、同じ素因数は避けた方がいい、
これ、実は少し考えなければいけないところではないかと思います。
例えば 13 をミラーラビンテストにかけるとします。
このとき、a = 3, 7, 11 という 3 つの素数で判定を行うことは有効でしょうか？
普通の自然数の世界では、7 は素数です。
しかし、13 をミラーラビンテストにかける場合、行う計算は全て mod 13 の世界です。
その世界では、3*11=7 ですから、7 はらすかるさんが仰るところの避けた方がいい数に該当します。
こう考えてみると、確率向上に貢献する a と貢献しない a の判別は「通常の自然数の世界で合成数だから」という単純な話ではない気がしています。
らすかるさん、DD++ さん。
「ミラーラビンの底には素数をとるのが良いのでしょうか？ 確率の評価に影響をあたえますか？」という私の疑問にお答えくださってありがとうございます。
私のほうでも調べてみたことがあります。
Miller-Rabin 素数判定法は確率的に素数らしい数かどうかを判定するのに有用ですが、
底のとりかたによっては、限定的な範囲内にて、確率100％で判定できる場合があります。注目点としては、この底の取り方です。
①
a = {2, 3, 5, 7, 11, 13, 17} を試せば 341550071728321 以下の素数判定を確率100％でできる。
②
a = {2, 3, 5, 7, 11, 13, 17, 19, 23} を試せば 3825123056546413051 以下の素数判定を確率100%でできる
うえの①、②では、底として素数のみの組を使っています。
なお、①、②はOEISの https://oeis.org/A014233 によります。
一定の範囲の数について素数判定を確率100%で判定するには
底としては素数の組を使うのがよいのかと
思ったところですが、一方において、これに反するような、
次のようなサイトがありました。
Deterministic variants of the Miller-Rabin primality test
http://miller-rabin.appspot.com/
上のサイトによれば7つの底を使って
2^64 までの数を確定的に素数判定できる底の例として
2, 325, 9375, 28178, 450775, 9780504, 1795265022
が挙げられています。
偶数か5の倍数かが、底になっていて
唖然としました。
悩みは続きます。
