ミラーラビン判定法で見誤ることになる整数のパターン
以前投稿していたデータを使うと
ミラー・ラビン法のStorong pseudoprimeの発見において
底を2,3,6の３つで[全部の底を満たす]調査すれば1～10^8までには
次の21個が発見でき
1373653;[829, 1; 1657, 1]=>p*(2*p-1)
1530787;[619, 1; 2473, 1]=>p*(4*p-3)
1987021;[997, 1; 1993, 1]=>p*(2*p-1)
2284453;[1069, 1; 2137, 1]=>p*(2*p-1)
3116107;[883, 1; 3529, 1]=>p*(4*p-3)
5173601;[929, 1; 5569, 1]=>p*(6*p-5)
6787327;[1303, 1; 5209, 1]=>p*(4*p-3)
11541307;[1699, 1; 6793, 1]=>p*(4*p-3)
13694761;[2617, 1; 5233, 1]=>p*(2*p-1)
15978007;[1999, 1; 7993, 1]=>p*(4*p-3)
16070429;[1637, 1; 9817, 1]=>p*(6*p-5)
16879501;[1453, 1; 11617, 1]=>p*(8*p-7)
25326001;[2251, 1; 11251, 1]=>p*(5*p-4)
27509653;[3709, 1; 7417, 1]=>p*(2*p-1)
27664033;[3037, 1; 9109, 1]=>p*(3*p-2)
28527049;[2389, 1; 11941, 1]=>p*(5*p-4)
54029741;[1733, 1; 31177, 1]=>p*(18*p-17)
61832377;[3517, 1; 17581, 1]=>p*(5*p-4)
66096253;[5749, 1; 11497, 1]=>p*(2*p-1)
74927161;[6121, 1; 12241, 1]=>p*(2*p-1)
80375707;[4483, 1; 17929, 1]=>p*(4*p-3)
の型で起こっている様です。
このリストは、
底として、2 およびに 3 だけを取ったときのものと同じになるようですね………
それはそうと、
p*(t*p-t+1)
のかたちになっているのですね。
DD++さんから、ミラーラビンは今話題にしている形での半素数に弱いのかというテーマが挙げられています。
必ずしも半素数にはならないようでしたので
以下にメモをあげます。
3215031751 は、
2, 3 をともに底としたときに
強擬素数です。
この数は
28351 * 113401
に等しく、また
113401 = 28351 * 4 -3
となっています。
私達がいま興味をもっていた形ですね。
さて、
113401 = 151*751
と素因数分解可能です。
このことから
3215031751 は半素数ではありません。
個人的には、半素数であるかどうかよりも、k と 2k-1 という値の大きさの関係を気にしていました。
その後、
・どうやら k+1 と 2k+1 という形に書いた方がよいこと
・2k+1 だけでなく mk+1 という形であれば m=2 という形かどうかはあまり重要でなさそうなこと
が見えてきていますね。
751 と 151 も、
151 = 150 + 1
751 = 5*150 + 1
ですから、同様の性質は持っていると言ってよさそうに思います。
2 と 3 とをともに含む
複数の底でミラー・ラビン判定を行い
結果が強擬素数であったとします。
この強擬素数が素数であるのか合成数であるかについてを更に調べたいと思ったとします。
この強擬素数を S とします。
まだ未証明ですが、次のような予想が成り立つとしましょう。すなわち。
S が合成数であるならば
自然数 k と m とがあって
S = (k +1)*(m*k +1) ………①
となる。
S が素数であるか合成数であるかを知りたいときに ① をあてにしてよいとするならば
単に、√S までの素数を列挙して
S をそれらで割ってみる素因数分解方法よりも速く素因数分解の結果が得られることがあるのでしょうか？
GAI さんによる 10^8 までの
強擬素数の素因数分解のリストを見るかぎり
どうやら m はかなり小さめです。
m について小さい順に調べると良いのではと思います。
①を、k についての２次方程式とみて
判別式が平方数になるかどうか検査すると
よいのではないかと山勘を働かせてみました。
さて、この方法は、本当に速く処理できるものなのでしょうか？
素因数分解できるまでの「平均時間」は圧倒的に速いと思います。
素因数分解ができるまでの「最悪の時間」はむしろ悪化すると思いますが。
つまり、最悪試さなきゃいけない候補の数は増えますが、当たりになる可能性が高いところだけを最初にピックアップして試せる感じになります。
たぶん。
DD++さん。
御意見をありがとうございました。
私の心象もそれに近いものがあります。
ここまでちょっと話を飛ばしすぎたきらいがありますので、以下では小まとめを。あとでログを見返したときにわかりやすいようにです。
2 およびに 3 を含む複数の底を使ってミラー・ラビン判定法を行います。その結果として合成数として判定されなかったものは強擬素数ですが、依然として合成数である確率がわずかながら残っています。今回はこの数を S と書くことにします。
観察によれば、S が合成数であるならば、m k を自然数として、
S = (k +1)*(m*k +1)
となることが期待されます。
なお、(k +1)、(m*k +1) については、素数であることを要請しません、念のため。
こうした m k を簡便に求められれば、
強擬素数 S が合成数であることの判定が簡便にできることとなります。 m k がみつけられなかったとしても、それは、合成数であることをこの手法では証明できなかっただけのことなので、強擬素数 S が素数であるとは限りません。
具体例をあげます。
S = 16697267137953148781
とします。
なお、この S は、底として、2, 3, 5, 7 を使ったミラー・ラビン法で強擬素数となるものです。
S = (k +1)*(m*k +1)
となる m k をみつけるために
k についての２次方程式とみたててこれを解くことを考えます。すなわち
m*k^2 +(m +1)*k +(1 -S) = 0
D = (m +1)^2 -4*m*(1 -S)
とおくと、この２次方程式の正の解は
k = (-(m +1) +√D)/(2*m)
となります。k が負の解は捨てます。
k が自然数であるための必要条件のひとつは
D が平方数であることです。
本当は、(2*m)で割っていますから、十分条件にはなっていません。
あとで確かめることにします。★★★
D = (m +1)^2 -4*m*(1 -S)
なのでしたが、これが平方数になるような m がうまく見つかるとありがたいわけです。
これまでの観察によれば、m はさほど大きな数にはならないようですので、m について、1 からはじめて順次カウントアップして探すこととします。
実際にやってみると、(プログラムが組めないので電卓でしました)
m = 6 で D が平方数となりました。
このときの D は
D = 400734411310875570769 = 20018351863^2
です。早くみつかってラッキー。この m をもとの２次方程式にほうりこんでやると
k = (-7 +√D)/(12)
= (20018351863 -7)/12
となります。
ちやんと 12 で割り切れればよいのですが……前に★★★で留意点としてあげていたことがここで確認されます。
実際に計算してみると
k = 1668195988
となります。★★★はクリアされました。
m = 6 でしたから
S は
S = (1668195988 +1)*(6*1668195988 +1)
となります。
検算すると
確かに、
S = 16697267137953148781
となります。
S は合成数と判定されました。
以上のように、比較的に簡便に合成数判定ができるケースが多くみられるのではないかとの予想をたててみています。
ミラー・ラビン判定法の補助手段として利用できたら嬉しいです。
言い忘れました。
16697267137953148781 は、底を 6 とすると合成数と判定されるそうです。
2 でも 3 でも強擬素数なのに。
k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
ですから、排除する必要はないのではないかと思います。
また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけることは成功します。
m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因数分解には成功するんじゃないかと思うのですが、どうなのでしょう。
> DD++さんが書かれました:
> また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけることは成功します。
> m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因数分解には成功するんじゃないかと思うのですが、どうなのでしょう。
アドバイスを有難うございます。
D = (m +1)^2 -4*m*(1 -S)
としていましたが、これを整理すると
D = (m -1)^2 +4*m*S
この D がある自然数 T の２乗になっていると
開平が出来て嬉しいのでした。
こうした T がみつかったときには
(m -1)^2 +4*m*S = T^2
となり、これを変形すれば
4*m*S = T^2 -(m -1)^2
4*m*S = (T +(m -1))*(T -(m -1))
となります。
仰るとおりに、
《4mS を 2 つの因数にわけることは成功します。》
とわかりました。
実用の範囲内で m が十分に小さいことがわかれば、
k を求めることを行わなくても
S の合成数判定ができるのですね、
おどろきです。
> DD++さんが書かれました:
> k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
> ですから、排除する必要はないのではないかと思います。
→
これ、意味をつかめませんでした。
よろしければご教示を賜りたくお願いいたします。
> 観察によれば、S が合成数であるならば、m k を自然数として、
S = (k +1)*(m*k +1)
となることが期待されます。
反例をようやくみつけました。
S = 196161196117261
は、底を 2, 3 としたミラー・ラビン判定法で強擬素数ですが、
S = 6602377*29710693
という半素数で、
k = 6602376
m = 29710692/6602376 = 9/2
となっています。
k が負の整数だと
S = (-101)*(-103)
みたいな形になるので、自然数の積にはなりません。
でも、これを見て自然数の積に書き直すのは容易ですよね、という話です。
> 反例
薄々そんな予感はしていましたが、やっぱり (mk+1)*(nk+1) の形も出てきましたか。
まあ、m も n も小さいという条件でなら、該当する数を探す労力はそんなに変わらないと思いますが。
その数S以前には
190131062354461,190847302523971,191212468762741,･･･
その数以降も
197201702068963,197867738963563,198675496474963,198888784469461,200262009366409,
200271411485473,200669198495977,201324851364883,･･･
等次々と見つかりますね。
その数S周辺しか調査しなかったのでもっと小さい数でも例外が見つかるような雰囲気ですね。
1150 の DD++ さん。
お返事をありがとうございます。
S = (k +1)*(m*k +1) ………①
ではなく、
S = (k -1)*(m*k -1)
の解を求められた、ということになるのですね、なるほど。
1153 の GAI さん。
(m*k+1)*(n*k+1)
のかたちでもよいとして
m や n が大きめのものってありますかね。
最初に GAI さんにご提示いただいた
10^8 までのリストでのトップは
m = 18 , n = 1でした。
実はさきの反例
S = 6602377*29710693
は、大きな m をひたすら電卓で
さがしていてみつけたのです。
m 捜し、こちらに興味があったものですから。
