素数と出会うのは素数大富豪の醍醐味ですね!(挨拶)
前提
筆者は3桁の素因数分解がほとんど瞬時にできます(1秒とします)。そこで4桁の試し割りは桁数を一つ下げれば計算することができるので(ここにもう1秒)、素数1つにつき2秒、60秒の制限時間では30個ほどの素数で試し割りでき、4桁の素数判定はほぼ確実に制限時間内に完了できるわけです。しかし、桁数が増えると、試し割り法で割る必要のある素数の個数が増えるだけでなく、下げなければならない桁数も増えていくため、伴ってかかる時間も増え(一桁当たり1秒)、制限時間内に試し割りできる素数の個数も減ります。したがって、5桁以上の知らない数については基本的にHNPが必要となります。
この記事では、試し割り法とフェルマー法の併用により、どのようにすれば効率的に素数判定を手計算や暗算で行うことができるかを確率を考慮しつつ議論した上で、60秒などの制限時間内で5~7桁の数に対して実際にどこまでHNP確率を上げられるのかを見ていきたいと思います。
手計算フェルマー法
素数判定や素因数分解のアルゴリズムは多数知られていますが、人間が手計算で使えそうなものは主に、試し割り法とフェルマー法の2つであると思います。このうち試し割り法についてはよく知られているのでフェルマー法について解説します。
フェルマー法とは、因数分解したい数Nに対し、N=a^2-b^2を満たす自然数a,bを見つけることでN=(a+b)(a-b)と因数分解する方法です。具体的にはa=[√N]+1から始め、a^2-Nを計算し、平方数になるかチェックすることをaを大きくしながら繰り返していきます。愚直にはaを1ずつ大きくしていきますが、手計算の範囲での効率化として、Nのmod10やmod9などの剰余を調べることで、ありうるaのmod10やmod9を絞ることができ、平方する必要のあるaの数を減らすことができます。次の表のとおりです。
(Nの剰余→aの剰余)の表
・mod10∧mod4
1→1,5,9/0,4,6
3→3,7/2,8
7→1,9/4,6
9→3,5,7/0,2,8Nのmod4が1なら/の左側、3なら右側
・mod9
1→1,8
2→0,3,6
4→2,7
5→0,3,6
7→4,5
8→0,3,6
・mod7
1→1,3,4,6
2→2,3,4,5
3→0,2,5
4→1,2,5,6
5→0,3,4
6→0,1,6
・mod11
1→1,2,4,7,9,10
2→0,4,5,6,7
3→1,2,5,6,9,10
4→2,3,4,7,8,9
5→3,4,5,6,7,8
6→0,2,3,8,9
7→0,1,4,7,10
8→0,1,3,8,10
9→1,3,5,6,8,10
10→0,2,5,6,9
・mod13
1→0,1,2,6,7,11,12
2→1,4,5,8,9,12
3→0,2,4,5,8,9,11
4→0,1,2,4,9,11,12
5→1,2,3,10,11,12
6→3,4,6,7,9,10
7→2,4,6,7,9,11
8→2,3,5,8,10,11
9→0,3,5,6,7,8,10
10→0,1,3,6,7,10,12
11→1,5,6,7,8,12
12→0,3,4,5,8,9,10
この剰余による絞り込みは7桁程度の数に対してはかなり有効です。mod9,10だけでも1/10~1/20に絞れ、さらに素数1つで絞るごとに1/2ほどになります。暗算で行う場合は、mod10,9,7あたりは記憶しておくとよいでしょう。
試し割り法とフェルマー法の併用
試し割り法では小さい素数から判定していくのが基本であるのに対して、フェルマー法では√Nに近い大きな素数から判定していくことができます。フェルマー法では√Nにaが近いほど効率よく判定でき、√N<a<(5/4)√Nの範囲を調べるだけで( (1/2)√N,√N)の区間に因数があるかどうか調べられますが、さらに( (1/3)√N,(1/2)√N)の区間を調べるには、aは(5/3)√Nまで計算する必要があります。すべての判定をフェルマー法で行うにはaはN/2ほどまで大きくする必要があり、圧倒的に効率が落ちていることが分かります。従って、試し割り法と組み合わせることでフェルマー法は最大の効果を発揮すると言えます。
限られた時間内に素数判定をして、HNP確率を上げることを考えると、ある素数pで割り切れないことが分かったとき、その数が素数である確率はp/p-1倍になったと考えられるため、始めは試し割りによって小さな素数について判定するのが効率が良いでしょう。しかし、ある程度まで割ってしまうと、素数1つの試し割りによる確率上昇の寄与が小さくなるため、フェルマー法を用いる方が効率よく確率を上げられるようになります。実際にこうなるか、具体的な状況を例に見ていきましょう。
Nが5桁の場合
Nが40000=200^2程度の場合を考えます。試し割り1回に3秒、フェルマー法のa1つあたりの2乗と引き算などの計算に15秒かかるとし、剰余により1/20に絞れたとします。
制限時間60秒では、67まで試し割り、a<1.02√Nまで、HNP確率:84%
制限時間120秒では、127まで試し割り、a<1.1√Nまで、HNP確率:99%
などとなり、ほとんど試し割り法で十分である一方、120秒ある場合など、数回はフェルマー法を使う方が計算が速くできることが分かります。
Nが6桁の場合
Nが360000=600^2程度の場合を考えます。試し割り1回に4秒、フェルマー法のa1つあたりに20秒かかるとし、剰余により1/20に絞れたとします。
制限時間60秒では、43まで試し割り、a<1.006√Nまで、HNP確率:62%
制限時間120秒では、109まで試し割り、a<1.006√Nまで、HNP確率:77%
フェルマー法の計算が重く、ほとんど試し割りという結果になりました。
Nが7桁の場合
Nが4000000=2000^2程度の場合を考えます。試し割り1回に5秒、フェルマー法のa1つあたりに30秒かかるとし、剰余により1/20に絞れたとします。
制限時間60秒では、31まで試し割り、a<1.0016√Nまで、HNP確率:49%
制限時間120秒では、83まで試し割り、a<1.0016√Nまで、HNP確率:60%
今度も同じようにフェルマー法はなかなか使えないという結果になりました。桁が増えるほど、フェルマー法があまり使えなくなるのは、√Nに近い素数の確率上昇の寄与がほとんどないためであると考えられます。十分に時間があり、完全な素数判定を行う場合などには、フェルマー法を用いた方が速いようです。
結論
頑張って試し割りしよう!