64bit の素数判定は7回の操作で完了する

Legalscape のしろくまです。
今日は確率的素数判定法について話したいと思います。

フェルマーの小定理

$p$ が素数のとき $p$ と互いに素な $a$ について

$a^{p-1} \equiv 1 \pmod{p}$

が成り立ちます

確率的素数判定法: フェルマーテスト

フェルマーの小定理の対偶を取ると、次のようなことが言えます。

$n$ と互いに素な $a$ について、 $a^{n-1} \not\equiv 1 \pmod{n}$ ならば、n は合成数である。

このことを利用した素数判定法をフェルマーテストといいます。
このような $a$ を $n$ が合成数である「証拠」と言うことにします。

実際に Python でフェルマーテストを実行してみると

# 91 = 13*7
print([pow(i, 91-1, 91) for i in range(2, 7)])
# [64, 1, 1, 64, 64]

# 68537611 = 4337*15803
print([pow(i, 68537611-1, 68537611) for i in range(2, 7)])
# [20955178, 68149251, 39398849, 8891250, 3002060]

という風にうまく合成数である証拠を見つけられているように見えます。
しかし、上述の $3^{90} \equiv 1 \pmod{91}$ のように合成数であって、 $a^{n-1} \equiv 1 \pmod{n}$ を満たすような a も存在し、そのような $a$ を「うそつき」ということにします。

このときランダムに $a$ を選んだとき嘘つきとなるような $a$ を選択する確率は $n$ がカーマイケル数でないならば高くとも 1/2 であることが知られています。
カーマイケル数とは合成数であって $\gcd(a,n) = 1$ なる任意の $a$ について $a^{n-1} \equiv 1 \pmod{n}$ を満たすような $n$ のことです。

証明は

$G$ を $(\mathbb{Z}/n\mathbb{Z})^\times$ の単元群（n と互いに素な剰余類の乗法群）とし、 $H$ を

$H = \lbrace a \in G \mid a^{n-1} \equiv 1 \pmod{n} \rbrace$

と定めます。
このとき $n$ が合成数でかつカーマイケル数ではないならば $H$ は $G$ の真部分群となります。これは

有限群についての事実:
指数 $|G:H| = |G|/|H|$ は $H$ が $G$ の真部分群であるならば $|G:H| \ge 2$ となる。

によって $|H| \le |G|/2$ となり、カーマイケル数以外に関してはランダムに選ばれた $a$ がフェルマーテストのうそつきとなる確率は $1/2$ 以下と分かります。

以上より、フェルマーテストを繰り返せば確率的に素数を判定できることがわかりました。
ちなみにカーマイケル数は無限に存在することが知られている一方で素数ほどは多くないので、カーマイケル数に巡り合わない場合はフェルマーテストで"運良く"十分な精度が得られる場合もあるかもしれません。

Miller-Rabin 素数判定法

一方で、そのような運要素を除去して確率を保証できるアルゴリズムとして Miller-Rabin 素数判定法が知られています。
Miller-Rabin 素数判定法も同様に素数が満たすべき性質をもとにした判定法です。
この方法にはカーマイケル数のような例外はなく 1 度の Miller-Rabin テストでランダムに選んだ $a$ がうそつきである確率は $1/4$ 以下となることが知られています。