ミラー・ラビン素数判定法への応用
以前56の後に1が18470個並ぶ莫大な数n=(505*10^18470-1)/9が素数であることをらすかるさんが
ミラー・ラビンの素数判定法を使ってほとんど素数であることは確かであると示されていた。
そこでこの確率的底aの選び方をaが例の奇素数の抜け穴(3,7,61,211）を2と共に指定して使えば
それでも素数の判定は可能であると思われた。
そこでWikipedia "ミラー–ラビン素数判定法"内のRubyによるコード
class Integer
def prime?
n = self.abs()
return true if n == 2
return false if n == 1 || n & 1 == 0
d = n-1
d >>= 1 while d & 1 == 0
20.times do
a = rand(n-2) + 1
t = d
y = ModMath.pow(a,t,n)
while t != n-1 && y != 1 && y != n-1
y = (y * y) % n
t <<= 1
end
return false if y != n-1 && t & 1 == 0
end
return true
end
end
module ModMath
def ModMath.pow(base, power, mod)
result = 1
while power > 0
result = (result * base) % mod if power & 1 == 1
base = (base * base) % mod
power >>= 1;
end
result
end
end
において20回繰り返すaの取り方(ランダムに選ばせる）
20.times do
a = rand(n-2) + 1
を base=[2,7,61,211]
base.each do |a|
へ変更して4つのaに限定させてプログラムを走らせてみました。
元のままのものでは12分ほどで
irb(main):033:0> n=(505*10**18470-1)/9;
irb(main):034:0* n.prime?
=> true
を返すが、変更したプログラムでは
3分ほどで同じく正しく判定してくれました。
GAIさん。
2, 7, 61 の三組の底では
4759123141 までの数について
確定的に素数判定ができるとのことです。
このミツグミは優秀なんですね……
上は、
http://miller-rabin.appspot.com/
をみてたら気がついたことです。
ええそうなんですよ。
だからもう一つ追加して
[2,7,61,211]の４つの素数を底に指定して、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）
がクリアーできれば、
莫大な奇数nでも合成数か素数かが正しく判定できるような気がしているんですが、その限界も
数値的確認もしてないので何とももどかしい所なんですが･･･
確か、有限個の底の組では
確率100%のミラーラビン判定ができないことが、既に証明されていると思います。
昔、調べたことがあるのですがそのことが書いてあるページがありました。
今、そのページのブクマでURLに飛んだら、
サイトが消失していました。
残念………
どこか探せばあるはずですが……
もちろん素数はそれこそ無限個あるので、全部の奇数に対して合成数か素数かを有限個の調査で調べ尽くすことは
不可能であろうことは想像できますが、ある有限の範囲以内においては、そのような判定できる組合わせはあっても
いいと思われますし、また確かにいろいろな調査で存在しています。
この組[2,7,61,211]がどこまでの範囲で大丈夫なのかは自分もわからないのですが、感じとしては相当莫大な有限の範囲を
保証できるのではないかという意味です。
GAIさん。了解いたしました。
以下のNは、ミラーラビン法により200未満の全ての素数を底にして検査した結果として
強擬素数と判定されたものです。変なところに改行がはいっていて申し訳ありませんが、
コピペミスを怖れた次第です。
N=
80383745745363949125707961434194210813883768828755
81458374889175222974273765333652186502336163960045
45791504202360320876656996676098728404396540823292
87387918508691668573282677617710293896977394701670
82304286871099974399765441448453411558724506334092
79022275296229414984230688168540432645753401832978
6111298960644845216191652872597534901
底を 211 で検査すると、ようやく合成数と判定できるようです。
Nはかなり大きな数ですね。
https://mathcrypto.wordpress.com/2014/11/23/large-examples-of-strong-pseudoprimes-to-several-bases/
を参考にいたしました。
上記のNが合成数であることを見るために、素因数分解を見つけようと試みているんですが
未だに発見できないでいます。
色々な方法の素因数分解でのアルゴリズムがあるようなんで、この方面に精通されている方で
上記を試みるとどんな因数を持っているか分かる方、お教え願います。
GAIさん。
次のふたつの素数の積なのだそうです。
2004791083197498027091532260422734265025940830205662543872531023690016085350598121358111595798609866791081582542679083484572616906958584643763990222898400226296015918301
4009582166394996054183064520845468530051881660411325087745062047380032170701196242716223191597219733582163165085358166969145233813917169287527980445796800452592031836601
（恥ずかしながら…汗…）検算はしておりません。いつもの知人に問い合わせたら、調べてくれて、結果を教わりました。
この2つの数は k と 2k-1 という関係にあるように見えます（目視確認）。
ミラーラビンテストって実は k(2k-1) という形の半素数と相性が悪かったりするんでしょうか？
GAI さんがおっしゃるに
> ええそうなんですよ。
> だからもう一つ追加して
> [2,7,61,211]の４つの素数を底に指定して、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）
> がクリアーできれば、
> 莫大な奇数nでも合成数か素数かが正しく判定できるような気がしているんですが、その限界も
> 数値的確認もしてないので何とももどかしい所なんですが･･･
調べてみました。
15070413782971 = 1171*19891*647011
で合成数です。
[2,7,61,211]の４つの素数を底にミラー・ラビン判定してみたところ、
Can be prime
となるようです。強擬素数判定ですね。
■確認方法
https://planetcalc.com/8995/
で、Miller–Rabin primality test
が可能です。
integer number 欄に
15070413782971
を入力します。前後に不可視なスペースが入ると叱られます。コピペの際には気をつけましょう。
bases 欄は random ではなく list にしましょう。
list としては、スペースで区切って
底を入力します。既定値は
3 5 7 11
となっていますのでこれを、今回は
2 7 61 211
と入れ直します。３箇所の区切り以外にスペースをいれると叱られるようです。
Details はオンにしたほうが面白いです。
Calculate ボタンを押下で
判定結果が返ります。
上の操作は、スマホでのものです。
パソコンだと違う？かもしれません。
お許し下さい。
Miller–Rabin primality test
のさきほどのオンラインツールが正確なのか不安ですので、
どなたか confirm をお願いいたします。
base を211単独でやればN;337桁で初めて擬素数を返す。
(2～199までの素数すべてをbase,または197,199の2つだけでbaseとしても同様な結果が起きる。)
のに対し
2,7,61,211の組合せでは以外に小さい14桁でのN=15070413782971(=1171*19891*64701)を偽判定してしまうのですね。
確かに
1171=1170+1
19891=17*1170+1
64701=553*1170+1
と相性が悪いものの構造になっているものなんですね。
全部をチェックしていませんが、この数値の周辺を観察してみたら判定は正しくされていることは
確認できました。（但しRubyのプログラムを利用して調べています。）
GAI さん。
文脈を追えないのでお教えいただきたいのですが……
>base を211単独でやればN;337桁で初めて擬素数を返す。
336桁以下の数ならば
確定的に素数判定ができるとのおかんがえでしょうか？
勘違いしてました。
例のNは211をbaseにしてチェックすれば擬素数と返すが、それより小さいものでも擬素数の判定を出すものはあるわけですね。
あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこれだ。
ということでいいでしょうか？
> "GAI"さんが書かれました:
> あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこれだ。
> ということでいいでしょうか？
15070413782971 は底を 11 のみで判定すると合成数と判定されるようです。従いまして
[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけても合成数と判定されると思います。何個か底を選んだときに、そのうちひとつでも合成数判定されると、底全体のテストで、合成数判定の結果を出すと思います。
また、底として、 197 または 199 のどちらかをひとつ指定しても、やはり合成数判定されます。
15070413782971 は
底として、2, 7, 61, 211 のどれかひとつを
指定すると、いずれにせよ
合成数判定されません。
2, 7, 61, 211 から何個か選んで判定しても
合成数判定されません。
今回は、2, 7, 61, 211 を底にしたときの強擬素数を探してみたのです。
とはいえ、依然として合成数である可能性は残されていますね。そこで、実際に因数分解してみたのでした。
