『はじめての数論』を読んでいきます.
今回は演習問題ログではありません.普通に読んでいきます.
\[
%%% 黒板太字 %%%
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
%%% カリグラフィー %%%
\newcommand{\calf}{\mathcal{F} }
\newcommand{\calg}{\mathcal{G} }
%%% 引数を取るもの %%%
\newcommand{\f}[2]{ \frac{#1}{#2} }
\newcommand{\im}{\operatorname{im} }
\]
今回の話の背景
本題に入る前に,素数判定について少し書きます.
フェルマーの小定理によって, 素数 $p$ について $\forall a \quad a^{p} \equiv a \mod p$ が成り立ちます.$a$ が $p$ で割れなければ $a^ p \equiv 1 \mod p$ です.
これを素数判定に利用することができます.
整数 $n$ が与えられて,この数が合成数かどうか調べたいものとします.
このとき適当な数 $1 \leq a \leq n-1$ をとって $a^ {n-1} \mod n$ を計算してみます.これが $1$ でなければ,フェルマーの小定理によって $n$ が素数でないことがわかります.
ここがポイントなのですが,$a^ {n-1} \mod n$ というのは繰り返し自乗法によって高速で求めることができます.だから,これは計算量的に「使える」判定法であるわけです.これをFermatテストといいます.
しかし $a^ {n-1} \not\equiv 1 \mod n$ であるような $a$ が見つかれば「$n$ は素数でない」と断言できますが,逆は正しいでしょうか?つまり,$n$ が合成数ならば必ず $a^ {n-1} \not\equiv 1 \mod n$ であるような $a$ を見つけられるでしょうか?
これが成り立っていれば大変うれしいですが,残念なことに答えはNOです.合成数であるにも関わらずFermatテストを突破してしまうものが存在します.これはカーマイケル数と呼ばれ,無限に存在します.*1
そこでより洗練された方法が必要になります.
Fermatの小定理の系として,次が従います.(本文には誤訳があって「いずれか」が「両方」になってるので注意)
命題
$p$ を奇素数とする.このとき $p-1$ は偶数なので
$$
p-1 = 2^ k q
$$
を満たす $k \geq 1$ と奇数 $q$ が存在する.ここで $p$ で割れない整数 $a$ が与えられたとする.
このとき,次のいずれかが成立する.
(1) $a^ q \equiv 1 \mod p$.
(2) $a^ q, a^ {2q}, \cdots , a^ {2^ {k-1}q}$ のうちの1つは $p$ を法として $-1$ に合同である.
(証明) $p$ は素数なので,$1$ の平方根は $\pm 1$ しかない.このことと,フェルマーの小定理から従う.□
この命題は裏を返せば,(1)(2) をどちらも満たさない整数 $1 \leq a \leq n-1$ が存在するならば,$n$ が合成数だと結論できるということです.
この事実に基づく素数判定法をラビン・ミラー法といいます.
そして,そのような(合成数であることの証拠となる) $a$ をラビン・ミラー証人といいます.
ラビン・ミラー法の素晴らしいところは,証人の数が保証できるところです.
なんと,次が成り立ちます.
$n$ が奇数の合成数のとき,$1$ から $n-1$ の間にある整数 $a$ のうち少なくとも $75$% は $n$ に対するラビンミラー証人である.
つまり,Fermatテストに対するカーマイケル数のような,都合の悪い数は存在しないわけです.単に存在しないだけでなく,この方法なら試行回数に応じて $n$ が素数である確率を急速に高めていくことができます.
素晴らしいですね.
ところが,この本には証明が載っていないのです.
同じ著者による『An Introduction to Mathematical Cryptography』でもなぜか載っていません.
The proof is not hard, but will not give it here.
Proposition 3.17
と書かれているだけです.なんじゃそりゃ.
証明は,訳者の鈴木治郎先生によると Koblitzの『数論アルゴリズムと楕円曲線暗号入門』の5.1章に掛かれているそうです.訳者さまありがとうね.(『A Friendly Introductiono to Number Theory』の本文には which is proved in more advanced texts と書かれているだけ)
他にも Shoup『A Computational Introduction to Number Theory and Algebra』にも証明が載っているようです.この Shoup の本は無料公開されているので,今回はこちらを参照することにします.
証明について
証明を紹介しようと思っていたのですが,思いのほか長かったのでやめます.
ポイントだけ書きます.
まず $n$ が偶数なら明らかに合成数なので,奇数に限定しておきます.
証明は $n$ の素因数の数による場合分けで行います.
$n$ が素数ベキのとき
$n$ の素因数が2つのとき
$n$ の素因数が3つ以上のとき
このうち,「$n$ が素数ベキのとき」は問題ありません.単数群が巡回群になりますので,フェルマー証人の時点でたくさんいます.わざわざラビンミラー証人を考えるという工夫がいらないケースです.
$n$ の素因数が2つ以上の時には,ラビンミラー証人の特殊な性質を使います.中国式剰余定理と,あとカーマイケル数の必要条件も使います.
Shoup『A Computational Introduction to Number Theory and Algebra』の10.2節に証明が載っていますので,気になるひとはそちらを見てください.(繰り返しますが,この Shoup の本は著者が無料公開してくださっています)
感想とまとめ
ラビン・ミラー判定法は,素数判定のための(いまのところ)非常に実用的なアルゴリズムです.
それがこれだけの代数的予備知識で理解できるなんて,すごいですね.コスパがいい.