パンの木を植えて

主として数学の話をするブログ

ラビン・ミラー判定法の証人の数 - 第19章

\[ %%% 黒板太字 %%% \newcommand{\A}{\mathbb{A}} %アフィン空間 \newcommand{\C}{\mathbb{C}} %複素数 \newcommand{\F}{\mathbb{F}} %有限体 \newcommand{\N}{\mathbb{N}} %自然数 \newcommand{\Q}{\mathbb{Q}} %有理数 \newcommand{\R}{\mathbb{R}} %実数 \newcommand{\Z}{\mathbb{Z}} %整数 %%% 2項演算 %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \]

『はじめての数論』を読んでいきます.

今回は演習問題ログではありません.普通に読んでいきます.

\[ %%% 黒板太字 %%% \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 の本は著者が無料公開してくださっています)


感想とまとめ

ラビン・ミラー判定法は,素数判定のための(いまのところ)非常に実用的なアルゴリズムです.

それがこれだけの代数的予備知識で理解できるなんて,すごいですね.コスパがいい.

*1:カーマイケル数が無限に存在することは1994年にアルフォード,グランヴィル,ポマランスによって証明されました