$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\arcsinh}{arcsinh} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\rot}{rot} \DeclareMathOperator{\grad}{grad} \DeclareMathOperator{\diver}{div} $

Fermat テストと Carmichael 数

Fermat テストとは、Fermat の小定理と呼ばれる代数学の基本的かつ重要な定理を用いた確率的素数判定法です。
現在、いくつかの効率の良い[1]確率的素数判定法が知られていますが、 その中でも有名な Solovay-Strassen 法や Miller-Rabin 法などのアルゴリズムは本記事で解説する Fermat テストの改良とみなすことができます。 その意味で Fermat テストは確率的素数判定法の「始祖」ともいえるでしょう。
しかしながら Fermat テストには Carmichael 数と呼ばれる「たちの悪い」合成数が存在することが知られており、 このアルゴリズムを実用に供することはできません。
従ってこのアルゴリズムを理解したところで実用上、ほとんど何の役にも立ちませんが、 前述のように著名な確率的素数判定法の(いしずえ)となっているものですから、 このアルゴリズムを理解することは、より高度な先述のアルゴリズムたちを理解する手助けとなることでしょう。

[1]多項式時間で判定が終了する、という意味

1Fermat テスト

1.1アイディア

Fermat の小定理とは以下のようなものでした。
定理 1: Fermatの小定理
$p$ を素数とする。このとき $p$ の倍数でない任意の整数 $a$ に対して、
\begin{equation} a^{p-1} \equiv 1 \mod p \end{equation}
(1)
が成り立つ。
この定理は $p$ が素数の場合には必ず成り立ちますが、 $p$ が素数でない場合には必ずしも成り立つとは限りません。 すなわち、上の合同式が成り立たないような $a$ を発見することができれば、 $p$ は素数ではないと結論することができます。 例えば $p = 6$ とすると、$a = 2$ のとき $a^{p-1} = 2^5 = 32 \equiv 2 \mod 6$ となるため、 $p = 6$ は素数ではない、すなわち合成数であると判断することができます。
この議論をもう少し明瞭にするために Fermat の小定理の対偶をとってみましょう。
命題 1: Fermatの小定理の対偶
$n$ を自然数とし、$a$ を整数とする。このとき、
\begin{equation} a^{n-1} \not\equiv 1 \mod n \end{equation}
(2)
が成り立つならば、$n$ は素数でないか、もしくは $n | a$ である。
従って与えられた整数 $n$ が素数であるかどうかを判定するためには $a = 1, 2, \cdots, n-1$ の中からランダムに値を選び出し、 その $a$ に対して $a^{n-1} \equiv 1 \mod n$ が成り立つかどうか確かめればよいことが分かります。 このようにして与えられた整数が素数かどうか判定するアルゴリズムを Fermat テスト といいます。
もし合同式が成り立たなければ、与えられた $n$ は自信を持って「合成数である」ということができます。 一方で合同式が成り立った場合には、与えられた $n$ は本当に素数であるか、 もしくは運悪く Fermat テストに合格してしまった偽りの合成数 (「偽素数(ぎそすう) (pseudoprime)」という) であるのかは判断することができません。 例えば $n = 15$ に対して $a = 4$ とすると $a^{n-1} = 4^{14} = 17895697 \equiv 1 \mod 15$ であり、 $n = 15$$a = 4$ によっては合成数であることを正しく判定できません。
しかしながら多くの異なる $a$ に対して Fermat テストを行えば行うほど Fermat テストは正しい答えを与えるでしょう。 このようにある確率でテストに失敗してしまうような素数判定法を特に 確率的素数判定法 といいます。 一方で確実に素数であるかどうかを判定できるアルゴリズムのことをこれと区別するために 決定的素数判定法 といいます。
このように Fermat テストでは与えられた整数が本当は合成数であるのに「素数である」と判定されてしまうことがあります。 他の確率的素数判定法もこの性質、すなわち「本当は合成数なのに素数であると判定してしまう」ことがあるため、 確率的素数判定法で「素数である」と判定された整数のことを 確率的素数 (probable prime) と呼ぶことがあります。

1.2アルゴリズム

Fermat テストの擬似コードを以下に掲載しておきます。
	function fermat_test(n, a){
		if(mod_pow(a, n-1, n) != 1) return false;  // mod_pow(a, b, m) は a^b (mod m) を返す
		return true;
	}

1.3計算量

Fermat テストの計算量ですが、上のコードを見てもらえば分かるとおり、時間のかかりそうな処理は mod_pow 函数ですが、 これは繰り返し二乗法を用いて $O(\log n)$ のステップ数で処理ができるため、 このアルゴリズムは高速に (多項式時間で) 動作することが分かります。

2Carmichael 数

2.1定義

一般には与えられた合成数 $n$ に対して運悪く Fermat の小定理の合同式を満たしてしまうような整数 $a$ はいくつか存在しますが、 そのような $a$ がかなりの割合で存在し、かなり多くのテストを行わないと合成数であることを正しく判定できないような 「たちの悪い」合成数が存在します。 そのような合成数を Carmichael 数(カーマイケルすう) といいます。
もう少し厳密な定義は以下の通りです。
定義 1: Carmichael 数
合成数 $n$ が任意の整数 $a$ に対して、$\gcd(a, n) = 1$ を満たすならば、
\begin{equation} a^{n-1} \equiv 1 \mod n \end{equation}
(3)
となるとき、合成数 $n$Carmichael 数 と呼ぶ。
定義の中で $\gcd(a, n) \neq 1$ の場合を排除しているのは、そのような $a$ はいかなる場合でも $a^{n-1} \not\equiv 1 \mod n$ となるからです。 証明は合同式の基礎的な練習問題となるので、是非チャレンジしてみてください[1]
Carmichael 数は小さい方から順に $561, 1105, 1729, 2465, 2821, \cdots$ となっています。 これらが実際に Carmichael 数であるかどうかを定義に沿ってチェックするのは大変ですが、 次に述べる Korselt の基準 というものを用いると比較的容易に判定することができます。 なお、Carmichael 数が無数に存在するかどうかは現在でも分かっていないそうです。。。

2.2Korselt の基準

次の命題が成り立つことが知られています。
命題 2: Korselt の基準 (Korselt's criterion)
整数 $n$ を合成数とする。このとき次の二つは同値である。
  1. $\forall a \in \mathbb{Z}, \gcd(a, n) = 1 \Rightarrow a^{n-1} \equiv 1 \mod n$ (先述の Carmichael 数の定義)
  2. $n$ は平方数で割り切ることができず (square-free)、かつ $\forall p | n$ なる素数 $p$ に対して $(p-1) | (n-1)$
これを満たす合成数を Carmichael 数と呼ぶ。
この命題 (の二番目の主張) を用いるとある整数が Carmichael 数であるかどうかを簡単に[2]判定することができます。 例えば最小の Carmichael 数 $561$ は、$561 = 3 \times 11 \times 17$ と素因数分解できるため、 平方数で割りきれないことは自明であり、$(3-1) | (561-1), (11-1) | (561-1), (17-1) | (561-1)$ が全て成り立つこともすぐに分かるため、 確かに $561$ は Carmichael 数であると分かります。
早速この命題の証明を行いましょう。 証明の中で中国の剰余定理、既約剰余類群の原始根の存在定理を用いています。
証明 1: 命題 2 (Korselt の基準) の証明
1. ならば 2. が成り立つこと、および 2. ならば 1. が成り立つことを証明する。
1. $\Rightarrow$ 2.
まず $n$ が偶数であると仮定すると、$a = -1$ のとき $a^{n-1} \equiv -1 \mod n$ であるが、 1. より $-1 \equiv 1 \mod n$ でなければならない。 しかしながらこれを満たすような合成数 $n$ は存在しない[3]。 よって $n$ は奇数である。 そこで $n$ を相異なる奇素数の積に次のように分解しよう。
\begin{equation} n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \end{equation}
(4)
ただし各 $p_i$ は互いに異なる奇素数であり、$e_i \geqslant 1, k \geqslant 1$ をみたす。 いま $(\mathbb{Z}/p_i^{e_i}\mathbb{Z})^\times$ は巡回群であることが知られているため、原始根が存在する。 その原始根を $a_i$ とおくと、中国の剰余定理から、
\begin{equation} \forall i, a \equiv a_i \mod p_i^{e_i} \end{equation}
(5)
をみたす整数 $a$ が存在する。 ここで $a, n$ は互いに素である。 なぜならば、$a$ がある $p_i$ で割り切れることを仮定すると、$a_i$$p_i$ で割り切れることとなり、 $a_i \in (\mathbb{Z}/p_i^{e_i}\mathbb{Z})^\times$ に矛盾する。 従って 1. から、このように構成された $a$ に対して、
\begin{align*} a^{n-1} & \equiv 1 \mod n \\ \Rightarrow a^{n-1} & \equiv 1 \mod p_i^{e_i} \\ \Leftrightarrow a_i^{n-1} & \equiv 1 \mod p_i^{e_i} \end{align*}
(6)
$a_i$ が原始根であることと、$a_i$ の位数が $\varphi(p_i^{e_i}) = p_i^{e_i-1} (p_i - 1)$ であることから、 $(p_i^{e_i-1} (p_i - 1)) | (n - 1)$ とならなければならない。 いま $p_i$$n - 1$ と互いに素であるから、これが成り立つためには $e_i = 1$ でなければならず、従って $(p_i-1) | (n-1)$ がいえる。 従って 2. が示された。
2. $\Rightarrow$ 1.
$n$ を相異なる素数の積に分解する。
\begin{equation} n = p_1 p_2 \cdots p_k \end{equation}
(7)
ただし各 $p_i$ は相異なる素数であり $k \geqslant 1$ である。 このとき $n$ と互いに素な任意の整数 $a$ に対して $p_i \not| a$ であるから、 Fermat の小定理が使えて $a^{p_i-1} \equiv 1 \mod p_i$ である。 2. より $(p_i - 1) | (n - 1)$ であるからこの合同式の両辺を $(n - 1) / (p_i - 1)$ 倍することができて、
\begin{equation} a^{n-1} \equiv 1 \mod p_i \end{equation}
(8)
これが任意の $i$ に対して成り立つため、結局、
\begin{equation} a^{n-1} \equiv 1 \mod n \end{equation}
(9)
が分かり、1. が示された。

2.3Fermat テストの弱点

このように Fermat テストには Carmichael 数というたちの悪い合成数、 すなわち殆ど全ての $a$ に対して Fermat テストに合格してしまう合成数が存在するため、 Fermat テストを実用としてそのまま用いることはできません。
しかしながらこのアルゴリズムに対して少しの改良を施すことで全ての合成数 $n$ に対して、 ランダムに $a$ を選んだとしてもある確率以下でしかテストが失敗しないようなアルゴリズムを構築することができれば、 十分多くの異なる $a$ に対してテストを繰り返せば「ほぼ確実に素数である」ということを自信を持って言うことができます。 例えば $1/2$ 以下の確率でしかテストが失敗しないようなアルゴリズムがあるとすれば、 そのテストを $100$ 回繰り返してもなお、 合成数であるのにも拘わらずテストが失敗している確率は $(1/2)^{100} = 7.89 \times 10^{-31}$ というとてつもなく小さな確率であり、 こうして「素数である」と判定された確率的素数が偽素数であると疑う人はまずいないでしょう。
実際にそのようなアルゴリズムはいくつか見つかっていますが、 歴史的に最も早く発見されたアルゴリズムは Solovay-Strassen の素数判定法と呼ばれるアルゴリズムで、 このアルゴリズムは最悪の場合でも $1/2$ の確率でしかテストが失敗しません。 また現在素数判定法として最もよく使われているアルゴリズムである Miller-Rabin の素数判定法は、 最悪の場合でも $1/4$ の確率でしかテストが失敗しません。 しかも計算量もコード量も Solovay-Strassen 法よりも少なく済みます。
Fermat ではありませんが、それらの素数判定法について詳しく解説するにはページが狭すぎるため、 また別の機会とさせていただくとして、本記事はここにて終了とさせていただきます。

[1]ヒント: 背理法を使う
[2]素因数分解を行う必要があるため、現時点では多項式時間で計算できるわけではありません。 ここでの「簡単に」というのは、愚直に定義どおりに確かめるよりは簡単、という意味です
[3]$n = 2$ ならばこの合同式は成り立つが、$2$ は素数である