素数マスターへの道(2)

フェルマーの小定理

フェルマーの小定理という、素数判定には欠かせない定理があります。
3,5,7,11という素数を使って、以下のような計算をしてみます。

2^ 3 = 8, 8 / 3 = 2 余り2
2^ 5 = 32, 32 / 5 = 6 余り2
2^ 7 = 128, 128 / 7 = 18 余り2
2^11 =2048, 2048 /11 = 186 余り2

2を3乗して、それを3で割ると、あまりが2になります。2を5乗して5で割っても、あまりは2になります。7,11,13,17,…と、素数を使ってこの計算をすると、必ず2になるのです。今、2という数字を使いましたが、他の数ではどうでしょうか？

3^ 3 = 27, 27 / 3 = 9 余り0
3^ 5 = 243, 243 / 5 = 48 余り3
3^ 7 = 2187, 2187 / 7 = 312 余り3
3^11 =177147, 177147 /11 =16104 余り3

3の場合は0になってしまいましたが、他はすべて3になっています。同じ数字を選んでしまった場合は必ず割り切れるので0になりますね。最初の例も、2の場合は割り切れて余りが0になってしまうので、使用する素数の中にわざと2を入れませんでした。でもまあ、2は素数って分かってるわけですし、あまり重要なことではありません。

とにかく、この定理を利用すれば、大きな素数の判別が出来そうです。

完璧では無い

実は、フェルマーの小定理は「ある数kが素数なら、2のk乗割るkのあまりが2になるYO！」というもので「あまりが2になったら素数ですYO！」とは限らないのです。素数とは限らないのですが、「素数である可能性が非常に高い」のは間違いありません。このとき、2以外の数で色々試してみて、やっぱり「素数臭い（￣ー￣）」となれば、ほぼ素数確定です。まあ、厳密ではありませんが、こうすると素数っぽい数字をかなり高い精度で発見することができます。

いやいや

フェルマーの小定理はなかなか役に立ちそう、ということはわかっても、よくよく考えてみると、大きな素数を扱うとき、たとえば1234567891という数字について調べるとき、割り算はまあ頑張るとして、「2の1234567891乗」なんて計算できないでしょ？
一休さんかなんかのお話でもありましたが、2倍を繰り返すと最初の方はあまり大きくない数でも、途中から膨大な数になっていきます。2の 1234567891乗を計算すると、3億桁以上の数になってしまって、それなら普通に2,3,5,7,…と試し割した方がずっと速そうです。

ですが、最終的な計算結果は「割り算のあまり」であって、少なくとも調べたい素数より小さいわけですから、あまりを得る計算に特化すれば、まあまあ手軽に計算することが出来ます。

繰り返し自乗法

ものすごく大きな累乗は計算できませんが、「ある数で割ったあまり」を求めるだけであれば、結構なスピードで計算することができます。具体的な数を使って計算してみましょう。

例)　2の301乗を301で割ったあまりを求めよう！

まず下準備として、2から始めて2乗を繰り返していきます。

2^ 2 = 4
2^ 4 = 4^2 = 16
2^ 8 = 16^2 = 256
2^16 = 256^2 = 65536

ここで、301を超えてしまったので、65536を301で割ったあまりを計算します。
65536 / 301 = 217 余り 219
余りが219なので、次の2乗は65536ではなく219を使います。
以下、同様の計算を繰り返していきます。

2^ 32 -> 219^2 = 47961, 47961 / 301 = 159 余り 102
2^ 64 -> 102^2 = 10404, 10404 / 301 = 34 余り 170
2^128 -> 170^2 = 28900, 28900 / 301 = 96 余り 4
2^256 -> 4^2 = 16

次は512乗で、301を超えてしまうので、ここで終わりにしておきます。

次に、(1,2,4,8,16,32,64,128,256)の数字を組み合わせて、301になるようにしてやります。一見難しそうですが、301から大きい順に引いていけば割と簡単です。

301 - 256 = 45
45 - 32 = 13
13 - 8 = 5
5 - 4 = 1

ですので、

301 = 1 + 4 + 8 + 32 + 256

のようになります。2の1乗は2ですので、これに先程計算したあまりを再びかけていきます。

2 * 16 * 256 * 102 * 16 = …

さすがに5つもかけると大きな数になるので、1回かけては301で割ったあまりを出して…という操作を繰り返します。

2 * 16 = 32
32 * 256 = 8192, 8192 / 301 = 27 余り 65
65 * 102 = 6630, 6630 / 301 = 22 余り 8
8 * 16 = 128

最終的に128になりました。2にならなかったので、301は素数じゃなかったということですね。(実際、301=7*43なので、7で割ることが出来ます)

この例だと、小さな数なので普通に試し割りする場合と割り算の回数はさほど変わらないのですが、大きな数になるほど有効になります。

2147483648に近い素数の場合、試し割りだけでやろうとすると約4800回も割り算をしなければなりませんが、繰り返し自乗法だとせいぜい60回程度の割り算で済みます。もちろん2乗の計算にも60回程度の掛け算が必要になりますが、掛け算の時間を考慮しても圧倒的に速いことがわかります。

続く