No.369 - 高校数学で理解する素数判定の数理 [科学]
\(\newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\mr}[1]{\mathrm{#1}} \newcommand{\br}[1]{\textbf{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\sb}{\subset} \newcommand{\sp}{\supset} \newcommand{\al}{\alpha} \newcommand{\sg}{\sigma}\newcommand{\cd}{\cdots}\)
今まで「高校数学で理解する・・・」という記事を何回か書きましたが、その中に暗号についての一連の記事があります。
No.310「高校数学で理解するRSA暗号の数理（１）」
No.311「高校数学で理解するRSA暗号の数理（２）」
No.313「高校数学で理解する公開鍵暗号の数理」
No.315「高校数学で理解する楕円曲線暗号の数理（１）」
No.316「高校数学で理解する楕円曲線暗号の数理（２）」
の５つです。これらは公開鍵暗号と、その中でも代表的な RSA暗号、楕円曲線暗号の数学的背景を書いたものです。情報通信をインフラとする現代社会は、この公開鍵暗号がなくては成り立ちません。"数学の社会応用" の典型的な例と言えるでしょう。
これらの暗号では、10進数で数10桁～数100桁の素数が必要です。ないしは、数10桁～数100桁の数が素数かどうかを判定する必要があります。
たとえば、マイナンバー・カードの認証に使われている RSA暗号の公開鍵は 2048ビットで、1024ビットの素数２つを掛け合わせて個人ごとに作られます。1024ビットということは \(2^{1023}\) ～ \(2^{1024}-1\) の数であり、10進では約300桁の巨大数です。素数を生成する式はないので、作るためには1024ビットの数をランダムに選び、それが素数かどうかを実用的な時間で判定する必要があります。
ビットコインのデジタル署名で使われているのは、256ビットの楕円曲線暗号です。この暗号の公開鍵は一般に公開されていますが（暗号の仕組みから個人ごとに作る必要はない）、この公開鍵を設計するときに必要なのは、256ビット＝約80桁（10進）の数が素数かどうかを判定することです。
つまり、公開鍵暗号の基礎となっている技術が「素数判定」なのです。そこで今回は、素数判定の方法で一般的な「Miller-Rabin テスト」の数学的背景を書きます。Miller、Rabin は、このテストを考案した数学者２人の名前です。
前提知識
本論に入る前に前提知識について整理します。「高校数学で理解する・・・」というタイトルは「高校までで習う数学の知識だけを前提とする」という意味です。従って、その前提からはずれるものはすべて証明するのが基本方針です。
今回は、以前の「高校数学で理解する・・・」で証明した事項を前提知識とします。
・合同式
・フェルマの小定理
・中国剰余定理
・オイラー関数
・群
です。また、暗号の記事ではありませんが、No.355「高校数学で理解するガロア理論（２）」の次の事項も前提とします。
・剰余群
・既約剰余類群
・巡回群
・群の直積
・群の同型
以下、剰余群以下の事項について、素数判定に関わるところを簡単に復習します。
剰余群
整数の集合を \(Z\) で表し、整数 \(n\) の倍数の集合を \(nZ\) とします。また、
\(\ol{j_n}\)
は、\(\bs{n}\) で割った余りが \(\bs{j}\) である整数の集合とします（剰余類と呼ばれる）。たとえば、\(n=9,\:j=2\) とすると、\(\ol{2_9}\) は「\(9\) で割ったら \(2\) 余る整数の集合」で、
\(\ol{2_9}=\{\:\cd,\:-16,\:-7,\:2,\:11,\:20,\:29,\:\cd\:\}\)
です。剰余群 \(Z/nZ\) とは、
\(Z/nZ=\{\ol{0_n},\:\ol{1_n},\:\cd\:,\:\ol{(n-1)_n}\}\)
で示される「無限集合を元とする有限集合」です。\(n=9\) だと、
\(Z/9Z=\{\ol{0_9},\:\ol{1_9},\:\ol{2_9},\:\ol{3_9},\:\ol{4_9},\:\ol{5_9},\:\ol{6_9},\:\ol{7_9},\:\ol{8_9}\}\)
です。この集合の元の加算 \(+\) を、
\(\ol{i_n}+\ol{j_n}=\ol{(i+j)_n}\)
と定義すると（右辺は整数のたし算）、\(Z/nZ\) はこの演算について群の定義を満たし（＝加法群）、この群を剰余群と呼びます。一般に有限群 \(G\) の元の数＝群位数を \(|G|\) で表しますが、剰余群の群位数は、
\(|Z/nZ|=n\)
です。以降、剰余類と整数を同一視して、
\(Z/9Z=\{0,\:1,\:2,\:3,\:4,\:5,\:6,\:7,\:8\}\)
というように書きます。従って、\(1\) は 整数の \(1\) を表すことも、また、\(Z/nZ\) の元（＝ \(n\) で割ると \(1\) 余る数の集合＝ \(\ol{1_n}\)）を表すこともあります。どちらかは文脈で決まります。
既約剰余類群
\(Z/nZ\) の元 \(\{0,\:1,\:\cd\:,\:j,\:\cd\:,\:n-1\}\) から \(\mr{gcd}(j,\:n)=1\) となる元（＝ \(n\) と素な元）だけを取り出した集合を既約剰余類群といい、\((Z/nZ)^{*}\) で表します。例をあげると、
\(\begin{eqnarray}
&&\:\:(Z/9Z)^{*}&=\{\ol{1_9},\:\ol{2_9},\:\ol{4_9},\:\ol{5_9},\:\ol{7_9},\:\ol{8_9}\}\\
&&&=\{\:1,\:2,\:4,\:5,\:7,\:8\:\}\\
\end{eqnarray}\)
です。この集合の、元と元との乗算 \(\cdot\) を、
\(\ol{i_n}\cdot\ol{j_n}=\ol{(ij)_n}\)
で定義すると（右辺の \(ij\) は整数の乗算）、\((Z/nZ)^{*}\) は乗算を演算とする群になります（＝乗法群）。従って、任意の元 \(a\in(Z/nZ)^{*}\) の逆元 \(a^{-1}\) が存在して、
\(a\cdot a^{-1}=1\)
が成り立ちます。つまり乗算と除算が自由にできます。\((Z/9Z)^{*}\) の例では、
\(\begin{eqnarray}
&&\:\:1^{-1}&=1&&\\
&&\:\:2^{-1}&=5, &5^{-1}&=2\\
&&\:\:4^{-1}&=7, &7^{-1}&=4\\
&&\:\:8^{-1}&=8&&\\
\end{eqnarray}\)
です。\((Z/nZ)^{*}\) の群位数は、オイラー関数 \(\varphi\) を使って、
\((Z/nZ)^{*}=\varphi(n)\)
で表されます。\(\varphi(n)\) は「\(n\) 以下で \(n\) とは互いに素な数の個数」です。\(p,\:q\) を異なる素数とすると、
\(\begin{eqnarray}
&&\:\:\varphi(p)&=p-1\\
&&\:\:\varphi(pq)&=(p-1)(q-1)\\
&&\:\:\varphi(p^2)&=p(p-1)\\
\end{eqnarray}\)
などが成り立ちます。
巡回群
\(p\) を奇素数（\(p\neq2\)）とすると、既約剰余類群 \((Z/pZ)^{*}\) は生成元 \(g\) をもちます。つまり、
\((Z/pZ)^{*}=\{\:g,\:g^2,\:g^,\:\cd\:,\:g^{p-1}=1\:\}\)
と表され、群位数は \(\varphi(p)=p-1\) です。このように、一つの生成元の累乗で全ての元が表せる群を巡回群と言います（\(1\) の次は再び \(g\) になって巡回する）。また、\(n\) が \(p\) の累乗、\(n=p^{\al}\:(\al\geq2)\) のときも \((Z/p^{\al}Z)^{*}\) は生成元をもつ巡回群です。\(\al=2\) のときの群位数は、
\(|(Z/p^2Z)^{*}|=\varphi(p^2)=p(p-1)\)
です。\((Z/9Z)^{*}\) の場合、群位数は \(\varphi(9)=6\) で、\(g=2\) と \(g=5\) が生成元になり、
\(\begin{eqnarray}
&&\:\:(Z/9Z)^{*}&=\{2,\:2^2=4,\:2^3=8,\:2^4=7,\:2^5=5,\:2^6=1\}\\
&&&=\{5,\:5^2=7,\:5^3=8,\:5^4=4,\:5^5=2,\:5^6=1\}\\
\end{eqnarray}\)
などと表せます。\(1,\:4,\:7,\:8\) は生成元ではありません。
群の直積、群の同型
\(G\) と \(H\) を有限群とし、その元を \(g_i\in G,\:h_j\in H\) として、２つの元のペア、
\((g_i,\:h_j)\) \((1\leq i\leq|G|,\:1\leq j\leq|H|)\)
を作るとき、すべてのペアを元とする集合を「群の直積」と言い、\(G\times H\) で表します。元と元の演算を \(g_i\) と \(h_i\) で個別に行うことで、直積も群になります。その群位数は、
\(|G\times H|=|G|\cdot|H|\)
です。
中国剰余定理によると、\(m,\:n\) が互いに素のとき、
\(x\equiv a\:\:(\mr{mod}\:m)\)
\(x\equiv b\:\:(\mr{mod}\:n)\)
の連立合同方程式は、\(mn\) を法として唯一の解を持ちます。\(x\) を \(m\) で割った余りを \(x_m\)、\(n\) で割った余りを \(x_n\) とし、
\(f\::\:x\:\longrightarrow\:(x_m,\:x_n)\)
の写像 \(f\) を定義すると、中国剰余定理によって \(f\) は１対１写像であり、かつ、
\(\begin{eqnarray}
&&\:\:f(xy)&=((xy)_m,\:\:(xy)_n)\\
&&&=((x_m\cdot y_m)_m,\:\:(x_n\cdot y_n)_n)\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:f(x)f(y)&=(x_m,\:x_n)\:(y_m,\:y_n)\\
&&&=((x_m\cdot y_m)_m,\:\:(x_n\cdot y_n)_n)\\
\end{eqnarray}\)
なので、
\(f(xy)=f(x)f(y)\)
が成り立ちます。また同様に \(f(x+y)=f(x)+f(y)\) であり、\(f\) は演算を保存する同型写像です。従って、剰余群 \(Z/mnZ\) は、２つの群の直積との間で "群の同型" が成り立ち、
\(Z/mnZ\cong Z/mZ\times Z/nZ\)
です（＝中国剰余定理の群による表現）。また 既約剰余類群 \((Z/mnZ)^{*}\) は、
\((Z/mnZ)^{*}\cong(Z/mZ)^{*}\times(Z/nZ)^{*}\)
と直積で表現できます。\(m,\:n\) がともに奇素数で \(m=p,\:n=q\:(\neq p)\)だと、
\((Z/pqZ)^{*}\cong(Z/pZ)^{*}\times(Z/qZ)^{*}\)
です。\((Z/pqZ)^{*}\) は巡回群でありませんが、２つの巡回群の直積で表現できることになります。
以上を前提として「Miller-Rabin テスト」のことを書きますが、これは「確率的素数判定アルゴリズム」の一種です。
「Miller-Rabin テスト」は「フェルマ・テスト」の発展形と言えるものです。そこでまず、「フェルマ・テスト」の原理になっている「フェルマの小定理」から始めます。
フェルマの小定理
素数がもつ重要な性質を示したのが、フェルマの小定理です。
この定理の \(a\) を、指数関数の「底（base）」と呼びます。偶数の素数は \(2\) しかないので、以降、\(\bs{n}\) は \(\bs{3}\) 以上の奇数として素数判定を考えます。フェルマの小定理を素数判定用に少々言い換えると、次のように表現できます。
このフェルマの小定理の対偶は次のようになります。
\(n\) が \(3\) 以上の奇数の合成数のとき、\(1\leq a\leq n-1\) について、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\)
\(a^{n-1}\not\equiv1\:\:(\mr{mod}\:n)\)
のどちらになるのか、\(a\) ごとに検討してみます。もちろん \(a=1\) なら \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) です。また、\(a=n-1\:(=-1)\) でも、\(n-1\) が偶数なので、 \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) です。
また、\(a\) が \(n\) と互いに素でないとき、つまり \(\mr{gcd}(n,\:a)\neq1\) ときは \(a^{n-1}\not\equiv1\:\:(\mr{mod}\:n)\) です。なぜなら、\(a\) と \(n\) の最大公約数を \(d\:(\neq1)\) として、もし \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) だとすると、
\(a^{n-1}=k\cdot n+1\:\:(k\) は整数\()\)
と表わせますが、
左辺について \(d\mid a^{n-1}\)
右辺について \(d\nmid(k\cdot n+1)\)
となってしまい、矛盾するからです。
\(a\neq1,\:n-1\)、 \(\mr{gcd}(n,\:a)=1\) のときにどうなるかは、\(a\) によって両方がありえます。ためにしに、\(n=21\) で計算してみると、
となります。色を塗った10個が \(a\neq1,\:n-1\)、 \(\mr{gcd}(n,\:a)=1\) のところですが、\(\equiv1\) \((a=8,\:13)\) と \(\not\equiv1\)（それ以外の8個）があることがわかります。とにかく、上の表で一つでも \(\bs{\not\equiv1}\) があれば、\(n\) は合成数だと判断できます。
このフェルマの小定理の対偶を利用して、巨大整数（数10桁～数100桁） \(n\) が素数かどうかを確率的に判定できます。つまり、\(1\leq a\leq n-1\) である数をランダムに、順々に選び、ある \(a\) がフェルマの条件に反すれば、その時点で \(n\) は合成数と判定します。何回か試行してすべての \(a\) がフェルマの条件に合致するなら（＝合成数だと判定できなければ）、\(n\) は素数の可能性が高い。
しかし困ったことに「合成数でありながら、多数の \(\bs{a}\) でフェルマの条件を満たしてしまう \(\bs{n}\)」が存在します。"カーマイケル数" です。最小のカーマイケル数は \(561=3\cdot11\cdot17\) ですが、\(\mr{gcd}(561,\:a)=1\) であるすべての \(a\:\:(1\leq a\leq560)\) で、
\(a^{560}\equiv1\:\:(\mr{mod}\:561)\)
が成り立ちます。その理由ですが、\(a\) を \(3,\:11,\:17\) のすべてと素な任意の数（＝ \(561\) と素な任意の数）とすると、フェルマの小定理より、
\(\begin{eqnarray}
&&\:\:a^{2}&\equiv1\:\:(\mr{mod}\:3)\\
&&\:\:a^{10}&\equiv1\:\:(\mr{mod}\:11)\\
&&\:\:a^{16}&\equiv1\:\:(\mr{mod}\:17)\\
\end{eqnarray}\)
が成り立ちます。\(560\) は、\(2,\:10,\:16\) 全部の倍数なので、それぞれの合同式の両辺を適切に累乗すると、
\(a^{560}\equiv1\:\:(\mr{mod}\:3)\)
\(a^{560}\equiv1\:\:(\mr{mod}\:11)\)
\(a^{560}\equiv1\:\:(\mr{mod}\:17)\)
が成り立つ。そうすると、中国剰余定理により、
\(a^{560}\equiv1\:\:(\mr{mod}\:3\cdot11\cdot17)\)
が成り立ちます。\(560\) 以下で \(561\) と素な数の個数は、オイラー関数 \(\varphi(n)\)（＝ \(n\) 以下で \(n\) と素な数の個数）を使うと、
\(\begin{eqnarray}
&&\:\:\varphi(561)&=\varphi(3)\varphi(11)\varphi(17)\\
&&&=2\cdot10\cdot16=320\\
\end{eqnarray}\)
なので、\(\dfrac{320}{560}=\dfrac{4}{7}\)、つまり半数以上の \(a\) でフェルマの条件が満たされることになります。これを一般的に言うと、カーマイケル数 \(c\) が３個の素数 \(p,\:q,\:r\) の積の場合、
\(\begin{eqnarray}
&&\:\:c&=pqr\\
&&\:\:\varphi(c)&=(p-1)(q-1)(r-1)\\
\end{eqnarray}\)
なので、この２つの比は、\(p,\:q,\:r\) が大きくなると \(1\) に近づきます。それは、ほとんど全ての \(a\:\:(1\leq a\leq c-1)\) がフェルマの条件を満たすことを意味します。
カーマイケル数は、特に \(n\) が巨大だと極めて希です。Wikipedia によると、「\(1\) から \(10^{21}\) の間には \(20,138,200\) 個のカーマイケル数があり、これはおよそ \(5\cdot10^{13}\) 個にひとつの割合」だそうです。しかし、カーマイケル数が無限個あることも証明されています。\(n\) が "運悪く" カーマイケル数だと、フェルマ\(\cdot\)テストでは素数と判定されてしまう。つまり、フェルマの条件を使って素数を確率的に判定するアルゴリズムには問題があるわけです。
Miller-Rabin の条件
そこで、素数の条件として、フェルマの条件とは別のものを考えます。フェルマの条件、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\)
において、\(n\) が素数とすると、\(n-1\) は偶数です。そこで、
\(n-1=2^ek\) （\(e\geq1,\:k\) は奇数）
と表します。この表記を用いて、\(a^{n-1}-1\) という式を因数分解すると、
\(\begin{eqnarray}
&&\:\:a^{n-1}-1&=a^{2^ek}-1\\
&&&=(a^{2^{e-1}k})^2-1\\
&&&=(a^{2^{e-1}k}+1)(a^{2^{e-1}k}-1)\\
&&&=(a^{2^{e-1}k}+1)((a^{2^{e-2}k})^2-1)\\
&&&=(a^{2^{e-1}k}+1)(a^{2^{e-2}k}+1)(a^{2^{e-2}k}-1)\\
&&& \vdots\\
\end{eqnarray}\)
と続きます。結局、因数分解は、
となります。これを \((\br{A})\) 式とします。\(n\) が素数のときは、フェルマの条件を変形すると、
\(a^{n-1}-1\equiv0\:\:(\mr{mod}\:n)\)
なので、フェルマの条件と等価な式は、
\((\br{A})\) 式の右辺 \(\equiv0\:\:(\mr{mod}\:n)\)
であり、ということは、
が成立します。\(\bs{n}\) が素数であるのがポイントです。\(n\) が合成数ならこんなことは言えません。このことより、\(n\) が素数であるための新たな条件が導けます。次項です。
素数の条件（Miller-Rabin）
\(a^{2^ik}\:\:(0\leq i\leq e-1)\) の \(e\) 個の数列を Miller-Rabin 系列と呼ぶことにします。
\(a^k,\:a^{2k},\:a^{4k},\:\cd\:,\:a^{2^{e-1}k}\)
です。この系列は、ある項の２乗が次の項になっています。従って \(\mr{mod}\:n\) でみて \(a^{2^rk}\equiv-1\) になれば、以降の項はすべて \(\equiv1\:(\mr{mod}\:n)\) になります。ということは、系列の中で \(\equiv-1\) となる項は「全く無い」か「一つだけある」のどちらかです。
ちなみに、Miller-Rabin による素数の条件の対偶は次の通りです。これを利用して合成数の判定ができます。
\(\bs{n}\) が素数であれば、フェルマーの条件と Miller-Rabin の条件は等価です。しかし、\(n\) が合成数のときは、フェルマの条件と Miller-Rabin の条件の意味が違ってきます。それが次です。
\(n\) が合成数のとき
\(n\) が合成数のときは、フェルマの条件から Miller-Rabin の条件を導くことはできません。なぜなら「\(n\)が素数」が導出のキーだからです。つまり、
とすると、\(a\in F\) であっても \(a\in M\) とは限らない。しかし、\((\br{A})\) 式でわかるように \(a\in M\) なら必ず \(a\in F\) です。従って、
\(M\:\subset\:F\)
です。ということは、数 \(a\) についてのフェルマーの条件によって \(n\) が合成数だと判定できなくても（つまり \(a\in F\)）、Miller-Rabin の条件で合成数と判定できる（つまり \(a\notin M\)）可能性があることになります。つまり合成数の判定においては、Miller-Rabin の条件はフェルマーの条件より厳格です。
しかも Miller-Rabin の条件は、合成数を合成数だと判定できる確率（ないしは判定できない確率）が、\(\bs{n}\) の値にかかわらず示せるのです。それが次の定理です。
Miller-Rabin の定理
\(\bs{n}\) がいかなる数であっても成り立つのがポイントです。実際に計算をしてみます。\(n\) を \(9\leq n < 10000\) である奇数の合成数とします。調べてみると、その総数は \(3771\)個です。そして、
とし、\(3771\)個の \(n\) のうち \(P\geq0.2\) のものをリストアップすると、次の５つだけです。
\(n=9\) のとき、\(P\) は最大値の \(0.25\) です。それ以降、\(n=1891\) のときに \(P\fallingdotseq0.24\) となりますが、\(0.25\) を越える \(n\) は（ \(9\leq n < 10000\) では）無いことがわかります。そしてこの定理は、\(\bs{n}\) がいかなる奇数の合成数であっても \(\bs{P\leq0.25}\) と主張しているわけです。
これでまず言えることは、Miller-Rabin の条件にとっての「カーマイケル数のような数」はあり得ないことです。
さらにこの定理によって、素数判定の信頼度を示すことができます。比喩で言うと次のとおりです。
以上の考え方で \(n\) の素数判定をするアルゴリズムが次です。
\(r=40\) だとすると、Miller-Rabin の素数判定アルゴリズムで「素数と判定したにもかかわらず実は合成数」の確率は、
\(\dfrac{1}{4^{40}}\) 以下
であることが保証されます。\(4^{40}\) は、\(\fallingdotseq\:1.2\times10^{24}\) で、\(10\)進数で\(25\)桁の数です。あまりに巨大すぎて想像するのは難しいのですが、たとえば、１秒の \(100\)万分の \(1\) の時間は \(1\) マイクロ秒で、\(1\) 秒間に地球を \(7.5\)周する光が \(300\)メートルしか進まない時間です。一方、宇宙の年齢は \(138\)億年程度と言われています。この宇宙の年齢をマイクロ秒で表すと、\(4.4\times10^{23}\) マイクロ秒です。ということは、\(4^{40}\) はその３倍近い数字です。
\(\dfrac{1}{4^{40}}\) は、数学的には \(0\) ではありませんが、確率としては実用的に \(0\) です。以上が Miller-Rabin の素数判定の原理です。
以降、 なぜ \(\dfrac{1}{4}\) 以下であると言えるのか、その証明をします。
定理を再度述べると次の通りです。
３つのケースにわけて証明します。以降の証明は、後藤・鈴木（首都大学東京）「Miller-Rabin素数判定法における誤り確率の上限」を参考にしました。
② ③ のケースは \(n\) が平方因子を持たないので ① と排他的であり、また ② と ③ も排他的です。いずれの場合も \(n\) が奇数なので、素因数に \(2\) は現れません。以降の３つのケースに分けた証明では、\(p\) を素数としたとき既約剰余類群 \((Z/pZ)^{*}\) 、\((Z/p^2Z)^{*}\) が巡回群であることを利用します。
１． \(n=p^2t\:\:(\:p\)は奇素数。\(t\geq1\) は奇数\()\)
Miller-Rabin の条件を満たす \(a\:(0\leq a\leq n-1)\) の集合を \(M\) とします。上で説明したように、\(n\) が合成数であったとしても Miller-Rabin の条件が成立すればフェルマの条件も成立します（\(n\) が合成数だとその逆は成り立たない）。従って、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\)
が成り立ちます。このフェルマの条件を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(F\) とすると、\(M\:\subset\:F\) なので元の数は、
\(|M|\leq|F|\)
です。さらに、\(p^2\mid n\)（＝ \(p^2\) が \(n\) を割り切る）なので、
も同時に成り立ちます。\((\br{B})\) 式を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(R_1\) とすると、\(a\in F\) なら \(a\in R_1\) なので、
\(\begin{eqnarray}
&&\:\:F&\subset R_1\\
&&\:\:|F|&\leq|R_1|\\
\end{eqnarray}\)
が成り立ちます。\(|M|\leq|F|\) とあわせると、
\(|M|\leq|R_1|\)
です。次に、剰余群 \(Z/p^2Z\) の元 で \((\br{B})\) 式を満たす \(a\:(0\leq a\leq p^2-1)\) の集合を \(R_2\) とします。\(x\in R_2\) だとすると、\(\mr{mod}\:p^2\) では、
\(\begin{eqnarray}
&&\:\:x&=x+p^2\\
&&&=x+2p^2\\
&&& \vdots\\
&&&=x+(t-1)p^2\leq p^2t-1\\
\end{eqnarray}\)
です。つまり、\((\br{B})\) 式を満たす \(Z/p^2Z\) の元１個に対して、\((\br{B})\) 式を満たす、\(0\leq a\leq n-1\:(p^2t-1)\) の \(t\)個の数が対応します。従って、
\(t|R_2|=|R_1|\)
です。\(|M|\leq|R_1|\) とあわせると、
\(|M|\leq t|R_2|\)
です。
剰余群 \(Z/p^2Z\) の元で \((\br{B})\) 式を満たすのは、\(p^2\) と互いに素な元だけです。つまり、既約剰余類群 \((Z/p^2Z)^{*}\) の元で \((\br{B})\) 式を満たすものの集合が \(R_2\) であるとも言えます。以降、 \((Z/p^2Z)^{*}\) を使って \(R_2\) の元の数、\(|R_2|\) を見積もります。それには \((Z/p^2Z)^{*}\) が巡回群であることを利用します。
一般に、巡回群においては次が成り立ちます。この定理を \((\br{C})\) とします。
【証明】
\(h=\mr{gcd}(m,\:d)\) とおく。位数 \(d\) の巡回群 \(G\) は、生成元 \(g\) を用いて、
\(G=\{g,\:g^2,\:g^3,\:\cd\:,\:g^{d-1},\:g^d=1\}\)
と表現できる。そこで \(x=g^i\:\:(1\leq i\leq d)\) と表すと、
\(\begin{eqnarray}
&&\:\:(g^i)^m&=1\\
&&\:\:g^{im}&=1\\
\end{eqnarray}\)
なので、\(im\) は群位数 \(d\) の整数倍である。つまり、
\(d\mid im\)
である。\(h=\mr{gcd}(m,\:d)\) として \(d\,'=\dfrac{d}{h}\) \(m\,'=\dfrac{m}{h}\) とおくと、
\(d\,'\mid im\,'\)
になるが、\(d\,'\) と \(m\,'\) は互いに素なので、
\(d\,'\mid i\)
である。つまり \(i\) は \(d\,'=\dfrac{d}{h}\) の倍数である。従って、\(1\leq i\leq d\) であることを考慮すると、
\(i=\dfrac{d}{h}\cdot j\:\:(1\leq j\leq h)\)
と表せる。つまり、\(x^m=1\) を満たす \(x\) の個数は \(h=\mr{gcd}(m,\:d)\) 個である。【証明終】
既約剰余類群 \((Z/p^2Z)^{*}\) は巡回群であり、群位数は\(\varphi(p^2)=p(p-1)\) です。従って、\((Z/p^2Z)^{*}\) の元で \(a^{n-1}=1\) を満たす元の数（\(=|R_2|\)）は定理 \((\br{C})\) により、
\(\begin{eqnarray}
&&\:\:|R_2|&=\mr{gcd}(p(p-1),\:n-1)\\
&&&=\mr{gcd}(p(p-1),\:p^2t-1)\\
\end{eqnarray}\)
となります。ここで、\(p^2t-1\) は \(p\) で割り切れないので、
\(\mr{gcd}(p(p-1),\:p^2t-1)=\mr{gcd}(p-1,\:p^2t-1)\)
ですが、この式の右辺は \(p-1\) 以下です。従って、
\(|R_2|\leq p-1\)
です。\(|M|\leq t|R_2|\) とあわせると、
\(|M|\leq t(p-1)\)
が得られました。従って、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&\leq\dfrac{t(p-1)}{tp^2-1}\\
&&&=\dfrac{p-1}{p^2-\dfrac{1}{t}}\\
\end{eqnarray}\)
となります。定義によって \(t\geq1,\:p\geq3\) ですが、上式の右辺は \(t\) についても \(p\) についても単調減少です。従って右辺の最大値は \(t=1,\:p=3\) のときで、
\(\dfrac{t(p-1)}{tp^2-1}\leq\dfrac{1}{4}\)
です。結論として、
\(\dfrac{|M|}{n-1}\leq\dfrac{1}{4}\)
となり、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は \(\dfrac{1}{4}\) 未満であることが証明されました。
ちなみに、この証明はフェルマの条件しか使っていません。つまり、
と言えます。ということは、平方因子をもつ数はカーマイケル数にはなりえないことが分かります。
２． \(n=p_1\cdot p_2\:(\:p_1,\:p_2\) は奇素数で \(p_1\neq p_2\:)\)
Miller-Rabin の定理を再掲します。
証明のポイントは２つあります。（２） の条件に関する Miller-Rabin 系列、
\(a^k,\:a^{2k},\:\:a^{4k},\:\cd\:,\:a^{(e-1)k}\)
を考えると、ある項の２乗が次の項なので、\(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) となる項があれば、それ以降の項は全て \(\equiv1\) となります。つまり、\(a^{2^rk}\equiv-1\) となる項は１つしかありません。従って、\(r\) を一つ決めたときに \(a^{2^rk}\equiv-1\) を満たす \(a\) の集合を \(A_2(r)\) とし、（２） を満たすすべての \(a\) の集合を \(A_2\) とすると、
\(|A_2|=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\)
が成り立ちます。さらに （１） の条件を満たす \(a\) の集合を \(A_1\) とすると、（１） と （２） は排他的です。従って、Miller-Rabin の条件を満たす \(a\) の集合を \(M\) とすると、
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&=|A_1|+\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\\
\end{eqnarray}\)
です。このことを以下の証明で利用します。もう一つの証明のポイントは、「１．\(\bs{n=p^2t\:\:(\:p}\) は奇素数。\(\bs{t\geq1}\) は奇数\(\bs{)}\)」での証明と同じように、巡回群の性質を利用することです。
まず前提として、Miller-Rabin の条件を満たす \(a\:(0\leq a\leq n-1)\) は、フェルマの条件、\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) も満たしますが、これが成り立つ \(a\) は \(n\) とは素です。従って、既約剰余類群 \((Z/nZ)^{*}\:=\:(Z/p_1p_2Z)^{*}\) の範囲で \(a\) の個数を検討します。
もちろん、\(p_1\neq p_2\) なので、既約剰余類群 \((Z/p_1p_2Z)^{*}\) は巡回群ではありません。しかし \(p_1,\:p_2\) が互いに素なので、\((Z/p_1p_2Z)^{*}\) は２つの既約剰余類群の直積と同型であり、
\((Z/p_1p_2Z)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\)
と表せます。つまり、\(a\in(Z/p_1p_2Z)^{*}\) とし、
\(a\) を \(p_1\) で割った余りを \(a_{p_1}\)
\(a\) を \(p_2\) で割った余りを \(a_{p_2}\)
と書くと、\(a_{p_1}\in(Z/p_1Z)^{*},\:\:a_{p_2}\in(Z/p_2Z)^{*}\) ですが、ここで、
\(f\::\:a\:\longrightarrow\:(a_{p_1},\:a_{p_2})\)
の写像を定義すると、この写像は１対１（全単射）で、同型写像であり、上の「直積と同型」の式が成り立ちます。同型写像は \(f(xy)=f(x)f(y)\) というように演算を保存するので、演算してから写像した結果と写像してから演算した結果は同じです。
また、この \((Z/p_1Z)^{*}\) と \((Z/p_2Z)^{*}\) は、\(p_1\) と \(p_2\) が素数なので、生成元をもつ巡回群です。それぞれの群位数は、
\(\begin{eqnarray}
&&\:\:|(Z/p_1p_2Z)^{*}|&=\varphi(p_1p_2)\\
&&&=(p_1-1)(p_2-1)\\
\end{eqnarray}\)
\(|(Z/p_1Z)^{*}|=\varphi(p_1)=p_1-1\)
\(|(Z/p_2Z)^{*}|=\varphi(p_2)=p_2-1\)
であり、
\(|(Z/p_1p_2Z)^{*}|=|(Z/p_1Z)^{*}|\cdot|(Z/p_2Z)^{*}|\)
が成り立ちます。ここで \((Z/p_1Z)^{*}\) の任意の部分集合を \(H_1\)、\((Z/p_2Z)^{*}\) の任意の部分集合を \(H_2\) とします。
\(H_1\subset(Z/p_1Z)^{*}\)
\(H_2\subset(Z/p_2Z)^{*}\)
です。\((Z/p_1p_2Z)^{*}\) の元 \(a\) で、
\(a_{p_1}\in H_1\)
\(a_{p_2}\in H_2\)
となる \(a\) を考え、このような \(a\) の集合を \(H\) と書くと、
\(f\::\:a\:\longrightarrow\:(a_{p_1},\:\:a_{p_2})\)
の写像は１対１対応であり（＝中国剰余定理）、集合の元の数については、
\(|H|=|H_1|\cdot|H_2|\)
が成り立ちます。
以上を踏まえて証明に進みます。一般に、
\(x\equiv y\:\:(\mr{mod}\:p_1p_2)\) なら
\(x\equiv y\:\:(\mr{mod}\:p_1)\) かつ \(x\equiv y\:\:(\mr{mod}\:p_2)\)
が言えます。また、\(p_1\) と \(p_2\) は互いに素なので、
\(x\equiv y\:\:(\mr{mod}\:p_1)\) かつ \(x\equiv y\:\:(\mr{mod}\:p_2)\) なら
\(x\equiv y\:\:(\mr{mod}\:p_1p_2)\)
も言えます。なぜなら、\(p_1\mid(x-y)\) かつ \(p_2\mid(x-y)\) なら、\(p_1p_2\mid(x-y)\) だからです。つまり、
\(x\equiv y\:\:(\mr{mod}\:p_1p_2)\)
\(x\equiv y\:\:(\mr{mod}\:p_1)\) かつ \(x\equiv y\:\:(\mr{mod}\:p_2)\)
の２つは、\(p_1,\:p_2\) が素数という前提では等価です。従って、Miller-Rabin の条件は次のように言い換えることができます。
このように言い換えて、\((Z/p_1p_2Z)^{*}\) での問題を、\((Z/p_1Z)^{*}\) と \((Z/p_2Z)^{*}\) の問題に置き換えます。Miller-Rabin の条件を満たす、
とすると、元の数については、
\(|M|=|M_1|\cdot|M_2|\)
が成り立ちます。以降、（１）\(,\) （２） の条件ごとに \(|M_1|\) と \(|M_2|\) を見積もることで、条件ごとの \(|M|\) を見積もり、そこから目的である \(|M|\) の数を評価します。（１）\(,\) （２） の条件ごとの \(M\) については、既に上で使ったように、
（１）を満たす \(M\) の部分集合を \(A_1\)
（２）を満たす \(M\) の部分集合を \(A_2\)
とします。
\(n-1=2^ek\) とおいたのと同じように、
\(p_1-1=2^{e_1}k_1\) （\(e_1\geq1,\:k_1\)：奇数）
\(p_2-1=2^{e_2}k_2\) （\(e_2\geq1,\:k_2\)：奇数）
とします。ここで、
\(e_1\leq e_2\)
とします。\(p_1\) と \(p_2\) は入れ替えてもよいので、こうすることで一般性は失われません。まず初めに、\(e,\:e_1,\:e_2\) の関係を整理しておきます。\(n-1=2^ek\) の式ですが、
\(\begin{eqnarray}
&&\:\:n-1&=p_1\cdot p_2-1\\
&&&=(2^{e_1}k_1+1)\cdot(2^{e_2}k_2+1)-1\\
&&&=2^{e_1+e_2}k_1k_2+2^{e_1}k_1+2^{e_2}k_2\\
&&&=2^{e_1}(2^{e_2}k_1k_2+k_1+2^{e_2-e_1}k_2)\\
\end{eqnarray}\)
と計算されます。この式を、
\(n-1=2^{e_1}\cdot K\)
\(K=2^{e_2}k_1k_2+k_1+2^{e_2-e_1}k_2\)
と表わすと、
\(e_1 < e_2\) のときは、\(K\) は奇数なので \(e=e_1\)
\(e_1=e_2\) のときは、\(K\) は偶数なので \(e > e_1\)
となり、いずれにせよ、
\(e_1\leq e\)
です。
以降、
\(e_1 < e_2\)
\(e_1=e_2\)
の２つに分けて証明します。
２．１ \(e_1 < e_2\) の場合
（１）が成立するとき
（１） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_1\) とします。巡回群に関する定理 \((\br{C})\) により、\((Z/pZ)^{*}\) の群位数は \(p-1\) なので、
\(a^k=1\) となる \((Z/p_1Z)^{*}\) の元は \(\mr{gcd}(k,\:p_1-1)\) 個
\(a^k=1\) となる \((Z/p_2Z)^{*}\) の元は \(\mr{gcd}(k,\:p_2-1)\) 個
です。また、\(n=p_1p_2\) のとき、
\((Z/nZ)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\)
の同型が成り立つので、
\(\begin{eqnarray}
&&\:\:|A_1|&=\mr{gcd}(k,\:p_1-1)\cdot\mr{gcd}(k,\:p_2-1)\\
&&&=\mr{gcd}(k,\:2^{e_1}k_1)\cdot\mr{gcd}(k,\:2^{e_2}k_2)\\
\end{eqnarray}\)
です。ここで、\(k,\:k_1,\:k_2\) は全て奇数です。従って、
\(\mr{gcd}(k,\:2^{e_1}k_1)=\mr{gcd}(k,\:k_1)\)
\(\mr{gcd}(k,\:2^{e_2}k_2)=\mr{gcd}(k,\:k_2)\)
が成り立ち、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
となります。ここで \(|A_1|\) の上限値を評価すると、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
であり、
\(|A_1|\leq k_1k_2\)
が結論づけられます。
（２）が成立するとき
（２） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_2\) とします。まず、\(0\leq r\leq e-1\) である \(r\) を一つ固定して考え、
\(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_1)\) かつ
\(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_2)\)
であるような集合を \(A_2(r)\) とします。そうすると、
\(|A_2|=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\)
が成り立ちます。まず、次を証明します。
【証明】
\((Z/p_1Z)^{*}\) は群位数 \(p_1-1\) の巡回群なので、その生成元を \(g\) とする。ここで、
\(g^{\frac{p_1-1}{2}}\)
を考えると、生成元の定義上、\(g^{p_1-1}=1,\) \(g^x\neq1\:(1\leq x < p_1-1)\) なので、
\(\begin{eqnarray}
&&\:\:g^{\frac{p_1-1}{2}}&\neq1\\
&&\:\:(g^{\frac{p_1-1}{2}})^2&=1\\
\end{eqnarray}\)
であり、つまり、
\(g^{\frac{p_1-1}{2}}=-1\:(=p_1-1)\)
である。\(a^{2^rk}=-1\) が成り立つ \(a\) を、生成元 \(g\) を用いて、
\(a=g^x\:\:(1\leq x\leq p_1-1)\)
と表すと、
だが、\(p_1-1=2^{e_1}k_1\) なので、
\(g^{2^rkx}=g^{2^{e_1-1}k_1}\)
が成り立つ。ここで一般的に \((Z/pZ)^{*}\) の生成元を \(g\) とし、
\(g^s=g^t\)
なら、\(j\) を整数として、
\(\begin{eqnarray}
&&\:\:g^{p-1}&=1\\
&&\:\:g^{j(p-1)}&=1\\
\end{eqnarray}\)
なので、
\(g^s=g^{t+j(p-1)}\)
である。つまり、
\(s\equiv t\:\:(\mr{mod}\:p-1)\)
が成り立つ。従って、
\(2^rkx\equiv2^{e_1-1}k_1\:\:(\mr{mod}\:p_1-1)\)
であり、\((\br{E})\) 式は \((\br{D})\) 式と等価である。\((\br{E})\) 式を解いて \(x\) を求めると、そこから \(a=g^x\) で \(a\) が求まる。
ここで、\(r\geq e_1\) と仮定すると、\((\br{E})\) 式は、
\(2^rkx-2^{e_1-1}k_1\equiv0\:\:(\mr{mod}\:2^{e_1}k_1)\)
と書ける。この \((\br{F})\) 式の \((2^{r-e_1+1}kx-k_1)\) の項に着目すると、\(r-e_1+1\geq1\) であり、\(k_1\) は奇数なので「偶数 － 奇数」＝「奇数」である。そうすると、\((\br{F})\) 式の左辺は \(2^{e_1-1}\) の奇数倍であり、法である \(2^{e_1}k_1\) では割り切れず、\((\br{F})\) 式は成り立たない。つまり、\(a^{2^rk}=-1\) の解は、\(r\geq e_1\) のときには無い。
一方、\(r < e_1\) のとき \((\br{E})\) 式は、
と書ける。この \((\br{F}\,')\) 式が成り立つためには、\((kx-2^{e_1-r-1}k_1)\) の項は約数として \(2^i\:(i\geq e_1-r\geq1)\) を持つ必要があるが（少なくとも偶数である必要）、\(kx\) と \(2^{e_1-r-1}k_1\) はともに奇数にも偶数にもなり得るので、 \((\br{F}\,')\) 式の成立可能性に問題はない。そこで、以降で \(r < e_1\) のときの \((\br{E})\) 式の解の個数を検討する。
において、
\(\begin{eqnarray}
&&\:\:h&=\mr{gcd}(k,\:k_1)\\
&&\:\:k\,'&=\dfrac{k}{h}\\
&&\:\:k_1{}^{\prime}&=\dfrac{k_1}{h}\\
\end{eqnarray}\)
とおく。\(k\,'\) と \(k_1{}^{\prime}\) は互いに素で、また、\(k,\:k_1\) が奇数なので、\(h,\:k\,',\:k_1{}^{\prime}\) は奇数である。\(r < e_1\) つまり \(r\leq e_1-1\) の条件があるので、\((\br{E})\) 式の両辺と法を \(2^rh\) で割ると、
となる。一般的に、
\(ax\equiv b\:\:(\mr{mod}\:m)\)
の合同方程式は、\(a\) が \(m\) と素なときには \(b\) の値にかかわらず解があって、その解は \(m\) を法として唯一である（下記）。
\((\br{G})\) 式 をみると、\(k\,'\) と \(k_1{}^{\prime}\) は互いに素であり、かつ奇数なので、\((\br{G})\) 式における \(k\,'\) と、法である \(2^{e_1-r}k_1{}^{\prime}\) は互いに素である。ということは、
\((\br{G})\) 式は、法 \(2^{e_1-r}k_1{}^{\prime}\) で唯一の解をもつ
ことになる。\((\br{G})\) 式は \((\br{E})\) 式の両辺と法を \(2^rh\) で割ったものであった。つまり、\((\br{G})\) 式の法は、
\(2^{e_1-r}k_1{}^{\prime}=\dfrac{2^{e_1}k_1}{2^rh}\)
である。ということは、\((\br{G})\) 式の、法 \(2^{e_1-r}k_1{}^{\prime}\) での唯一の解は、法 \(2^{e_1}k_1\) である \((\br{E})\) 式の解、\(2^rh=2^r\cdot\mr{gcd}(k,\:k_1)\) 個に対応する。\((\br{E})\) 式は \((\br{D})\) 式と等価なので、これで、
が証明できた。【証明終】
ここまでで、
\((Z/p_1Z)^{*}\) において \(a^{2^rk}=-1\) である \(a\) の個数は
\(r\geq e_1\) のとき \(0\) 個
\(r < e_1\) のとき \(2^r\cdot\mr{gcd}(k,\:k_1)\) 個
であることが分かりました。この議論は \((Z/p_2Z)^{*}\) のときにも全く同じようにできて、
\((Z/p_2Z)^{*}\) において \(a^{2^rk}=-1\) である \(a\) の個数は
\(r\geq e_2\) のとき \(0\) 個
\(r < e_2\) のとき \(2^r\cdot\mr{gcd}(k,\:k_2)\) 個
が言えます。この結果を踏まえて、
を求めます。これは、
\((Z/p_1p_2Z)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\)
の直積関係を利用すると、\(e_1 < e_2\) の関係を考慮して、
\(r < e_1\) のとき
\(\begin{eqnarray}
&&\:\: |A_2(r)|&=2^r\cdot\mr{gcd}(k,\:k_1)\cdot2^r\cdot\mr{gcd}(k,\:k_2)\\
&&&=4^r\cdot\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\\
\end{eqnarray}\)
\(r\geq e_1\) のとき
\(|A_2(r)|=0\)
となります。ここから \(|A_2|\) を計算するには、
\(|A_2|=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\)
ですが、\(e_1\leq e\) の関係があるので、\(e-1\) までの総和は \(e_1-1\) までの総和に等しいことになります。つまり、
\(\begin{eqnarray}
&&\:\:|A_2|&=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\\
&&&=\displaystyle\sum_{r=0}^{e_1-1}|A_2(r)|\\
&&&=\displaystyle\sum_{r=0}^{e_1-1}4^r\cdot\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\\
\end{eqnarray}\)
の式が成り立ちます。この式に等比数列の総和である、
\(\displaystyle\sum_{r=0}^{e_1-1}4^r=\dfrac{4^{e_1}-1}{4-1}=\dfrac{4^{e_1}-1}{3}\)
を代入すると、
\(|A_2|=\dfrac{4^{e_1}-1}{3}\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
です。ここで、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
の関係を利用すると、
\(|A_2|\leq\dfrac{4^{e_1}-1}{3}k_1k_2\)
となります。ここまでの式は、\(e_1 < e_2\) でなくても \(e_1\leq e_2\) なら成り立つことが導出過程から分かります。
以上の計算で \(|M|\) を評価できます。
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&\leq k_1k_2+\dfrac{4^{e_1}-1}{3}k_1k_2\\
\end{eqnarray}\)
この計算をもとに \(1\leq a\leq n-1\) の \(n-1\) 個のうちの \(|M|\) の割合を評価すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&=\dfrac{|M|}{p_1p_2-1}\\
&&& < \dfrac{|M|}{(p_1-1)(p_2-1)}\\
&&&=\dfrac{|M|}{2^{e_1}k_1\cdot2^{e_2}k_2}\\
&&&\leq\dfrac{1}{2^{e_1+e_2}}\left(1+\dfrac{4^{e_1}-1}{3}\right)\\
&&&=\dfrac{1}{2^{e_1+e_2}}\cdot\dfrac{2+4^{e_1}}{3}\\
\end{eqnarray}\)
となります。ここで、\(\bs{e_1 < e_2}\) なので、\(\bs{2e_1+1\leq e_1+e_2}\) です。従って、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{2^{2e_1+1}}\cdot\dfrac{2+4^{e_1}}{3}\\
&&&=\dfrac{2+4^{e_1}}{6\cdot4^{e_1}}\\
\end{eqnarray}\)
ですが、この最後の式の最大値は \(e_1=1\) のときです。これを代入すると、
\(\dfrac{|M|}{n-1} < \dfrac{6}{24}=\dfrac{1}{4}\)
となって、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は \(e_1 < e_2\) のときに \(\dfrac{1}{4}\) 未満であることが証明されました。
２．２ \(e_1=e_2\) の場合
（１）が成立するとき
\(e_1 < e_2\) と全く同じ考え方で、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
です（\(k,\:k_1,\:k_2\) は奇数）。ここで、一般的には、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
が成り立ちますが、\(e_1=e_2\) だと、
\(\mr{gcd}(k,\:k_1)=k_1\)
\(\mr{gcd}(k,\:k_2)=k_2\)
が同時に成り立つことはありません。なぜなら、同時に成り立つとすると、
\(k_1\mid k\) かつ \(k_2\mid k\)
ですが、\(n-1=2^ek\) だったので、
\(k_1\mid(n-1)\) かつ \(k_2\mid(n-1)\)
です。ここで、\(n-1\) は
\(\begin{eqnarray}
&&\:\:n-1&=p_1p_2-1\\
&&&=(1+2^{e_1}k_1)\cdot p_2-1\\
&&&\equiv p_2-1\:\:(\mr{mod}\:k_1)\\
\end{eqnarray}\)
となりますが、\(k_1\mid(n-1)\) なので、
\(k_1\mid(p_2-1)\)
\(k_1\mid2^{e_2}k_2\)
\(k_1\mid k_2\)
となります。まったく同様にして、
\(n-1\equiv p_1-1\:\:(\mr{mod}\:k_2)\)
\(k_2\mid(p_1-1)\)
\(k_2\mid2^{e_1}k_1\)
\(k_2\mid k_1\)
です。\(k_1\mid k_2\) かつ \(k_2\mid k_1\) ということは、\(k_1=k_2\) ですが、\(e_1=e_2\) なので、\(p_1=p_2\) となって矛盾します。つまり \(\mr{gcd}(k,\:k_1)=k_1\)、\(\mr{gcd}(k,\:k_2)=k_2\) が同時に成り立つことはありません。そこで、
\(\mr{gcd}(k,\:k_1) < k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
として一般性を失いません。ここで \(k_1\) を素因数分解したときに現れる最小の素数を \(q\:(q\geq3)\)とし、
\(k_1=q\cdot k_0\:\:(k_0\)：奇数\()\)
と表します。そうすると、\(\mr{gcd}(k,\:k_1) < k_1\) なので、
\(\mr{gcd}(k,\:k_1)\leq k_0\)
が成り立ち、
\(\dfrac{k_1}{\mr{gcd}(k,\:k_1)}\geq\dfrac{k_1}{k_0}=q\geq3\)
となります。ここから、
\(\mr{gcd}(k,\:k_1)\leq\dfrac{1}{3}k_1\)
が得られます。そこで、
\(\mr{gcd}(k,\:k_1)\leq\dfrac{1}{3}k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
をもとに、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
を評価すると、
\(|A_1|\leq\dfrac{1}{3}k_1k_2\)
となります。
（２）が成立するとき
このケースは \(e_1 < e_2\) で導出した、
\(|A_2|\leq\dfrac{4^{e_1}-1}{3}\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
までは全く同じです。ここで、
\(\mr{gcd}(k,\:k_1)\leq\dfrac{1}{3}k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
によって評価すると、
\(|A_2|\leq\dfrac{1}{3}\cdot\dfrac{4^{e_1}-1}{3}k_1k_2\)
が成り立ちます。
以上の計算から \(|M|\) を評価すると、
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&\leq\dfrac{1}{3}k_1k_2+\dfrac{1}{3}\cdot\dfrac{4^{e_1}-1}{3}k_1k_2\\
\end{eqnarray}\)
この計算をもとに \(1\leq a\leq n-1\) の \(n\) 個のうちの \(|M|\) の割合を計算すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&=\dfrac{|M|}{p_1p_2-1}\\
&&& < \dfrac{|M|}{(p_1-1)(p_2-1)}\\
&&&=\dfrac{|M|}{2^{e_1}k_1\cdot2^{e_2}k_2}\\
&&&\leq\dfrac{1}{2^{e_1+e_2}}\cdot\dfrac{1}{3}\left(1+\dfrac{4^{e_1}-1}{3}\right)\\
&&&=\dfrac{1}{2^{2e_1}}\cdot\dfrac{1}{3}\cdot\dfrac{2+4^{e_1}}{3}\\
&&&=\dfrac{1}{4^{e_1}}\cdot\dfrac{1}{3}\cdot\dfrac{2+4^{e_1}}{3}\\
&&&=\dfrac{1}{3}\left(\dfrac{2}{3\cdot4^{e_1}}+\dfrac{1}{3}\right)\\
\end{eqnarray}\)
となります。この最後の式の最大値は \(e_1=1\) のときです。代入すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{3}\left(\dfrac{1}{6}+\dfrac{1}{3}\right)\\
&&&=\dfrac{1}{6} < \dfrac{1}{4}\\
\end{eqnarray}\)
となって、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は、\(e_1=e_2\) のときにも \(\dfrac{1}{4}\) 未満であることが証明されました。
３． \(n=p_1\cdot p_2\cdot\cd\cdot p_m\:\:(\:m\geq3\:)\)
\(n\) が３個以上の相異なる奇素数の積に素因数分解される場合です。この場合も、基本的には \(n=p_1\cdot p_2\) のケースと（全く同じではないが）同様になります。Miller-Rabin の定理を再掲します。
以降、表記を見やすくするため、\(m=3\)、\(n=p_1\cdot p_2\cdot p_3\) の場合で記述します。既約剰余類群の同型関係、
\((Z/p_1p_2p_3Z)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\times(Z/p_3Z)^{*}\)
を利用して、問題を置き換えます。それぞれの群位数は、
\(\begin{eqnarray}
&&\:\:|(Z/p_1p_2p_3Z)^{*}|&=\varphi(p_1p_2p_3)\\
&&&=(p_1-1)(p_2-1)(p_3-1)\\
\end{eqnarray}\)
\(|(Z/p_1Z)^{*}|=\varphi(p_1)=p_1-1\)
\(|(Z/p_2Z)^{*}|=\varphi(p_2)=p_2-1\)
\(|(Z/p_3Z)^{*}|=\varphi(p_3)=p_3-1\)
であり、
\(|(Z/p_1p_2p_3Z)^{*}|=|(Z/p_1Z)^{*}|\cdot|(Z/p_2Z)^{*}|\cdot|(Z/p_3Z)^{*}|\)
が成り立ちます。Miller-Rabin の条件は次のように言い換えられます。
例によって、
\(p_1-1=2^{e_1}k_1\:\:(e_1\geq1,\:k_1\) は奇数\()\)
\(p_2-1=2^{e_2}k_2\:\:(e_2\geq1,\:k_2\) は奇数\()\)
\(p_3-1=2^{e_3}k_3\:\:(e_3\geq1,\:k_3\) は奇数\()\)
とおきますが、\(\bs{e_1}\) は \(\bs{e_1,\:e_2,\:e_3}\) のうちの最小とします。こう仮定して一般性を失うことはありません。この仮定のもとでは、
\(3e_1\leq e_1+e_2+e_3\)
が成り立ちます。等号は \(e_1=e_2=e_3\) の場合です。
（１）が成立するとき
（１） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_1\) とします。\(n=p_1\cdot p_2\) のケースと同様の計算によって、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\cdot\mr{gcd}(k,\:k_3)\)
となります。\(|A_1|\) の上限値を評価すると、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
\(\mr{gcd}(k,\:k_3)\leq k_3\)
なので、
\(|A_1|\leq k_1k_2k_3\)
が結論づけられます。
（２）が成立するとき
（２） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_2\) とします。\(n=p_1\cdot p_2\) のケースと同様の計算で、
\(|A_2|=\displaystyle\sum_{r=0}^{e_1-1}(2^r)^3\cdot\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\cdot\mr{gcd}(k,\:k_3)\)
です。この式に \(e_1\) だけが現れるのは、\(e_1\) が \(\{e_1,\:e_2,\:e_3\}\) の最小値だからです。ここで、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
\(\mr{gcd}(k,\:k_3)\leq k_3\)
の関係を利用します。また、等比数列の総和を計算すると、
\(\begin{eqnarray}
&&\:\:\displaystyle\sum_{r=0}^{e_1-1}(2^r)^3&=\displaystyle\sum_{r=0}^{e_1-1}(2^3)^r\\
&&&=\dfrac{(2^3)^{e_1}-1}{2^3-1}\\
\end{eqnarray}\)
です。まとめると、
\(|A_2|\leq\dfrac{2^{3e_1}-1}{2^3-1}\cdot k_1k_2k_3\)
が得られます。
以上をもとに \(|M|\) を評価すると、
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&\leq k_1k_2k_3+\dfrac{2^{3e_1}-1}{2^3-1}\cdot k_1k_2k_3\\
\end{eqnarray}\)
です。この計算をもとに \(1\leq a\leq n-1\) の \(n-1\) 個のうちの \(|M|\) の割合を計算すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&=\dfrac{|M|}{p_1p_2p_3-1}\\
&&& < \dfrac{|M|}{(p_1-1)(p_2-1)(p_3-1)}\\
&&&=\dfrac{|M|}{2^{e_1}k_1\cdot2^{e_2}k_2\cdot2^{e_3}k_3}\\
&&&\leq\dfrac{1}{2^{e_1+e_2+e_3}}\left(1+\dfrac{2^{3e_1}-1}{2^3-1}\right)\\
\end{eqnarray}\)
となります。ここで、\(3e_1\leq e_1+e_2+e_3\) です。従って、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{2^{3e_1}}\left(1+\dfrac{2^{3e_1}-1}{2^3-1}\right)\\
&&&=\dfrac{6+2^{3e_1}}{7\cdot2^{3e_1}}\\
\end{eqnarray}\)
ですが、この最後の式は \(e_1\) の増大によって単調減少するので、その最大値は \(e_1=1\) のときです。これを代入すると、
\(\dfrac{|M|}{n-1} < \dfrac{6+8}{56}=\dfrac{1}{4}\)
となって、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は \(\dfrac{1}{4}\) 未満であることが確かめられました。
以上の表記は \(m=3\) の場合ですが、証明のプロセスを振り返ってみると、\(m\geq3\) のときは、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{2^{m\cdot e_1}}\left(1+\displaystyle\sum_{r=0}^{e_1-1}(2^m)^r\right)\\
&&&=\dfrac{1}{2^{m\cdot e_1}}\left(1+\dfrac{2^{m\cdot e_1}-1}{2^m-1}\right)\\
&&&=\dfrac{2^m-2+2^{m\cdot e_1}}{(2^m-1)\cdot2^{m\cdot e_1}}\\
\end{eqnarray}\)
です。この式の右辺は \(e_1\) について単調減少なので、\(e_1=1\) を代入すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{2^m-2+2^m}{(2^m-1)\cdot2^m}\\
&&&=\dfrac{2\cdot(2^m-1)}{(2^m-1)\cdot2^m}\\
&&&=\dfrac{1}{2^{m-1}}\\
&&&\leq\dfrac{1}{4}\\
\end{eqnarray}\)
が \(m\geq3\) のすべてで成り立ちます。
ちなみに、カーマイケル数は必ず、\(p_1\cdot p_2\cdot\cd\cdot p_m\) \((\:m\geq3\:)\) の形をしていることが知られています。上の証明によって、\(n\) がカーマイケル数であったとしても Miller-Rabin の条件を満たす底 \(a\) は 全体の \(\dfrac{1}{4}\) 未満であることが分かります。
以上で、Miller-Rabin の定理が証明されました。
Miller-Rabin の定理を使って、実際に巨大素数を求めてみます。2048 ビットの RSA 暗号で使われる 1024 ビットの素数を求めます。1024 ビットは、\(2^{1023}\) ～ \(2^{1024}-1\) の数です。Python で整数 n が素数かどうかを判定する関数、miller_rabin(n) を次のようにシンプルに実装します。n が素数なら True、合成数なら False を返す関数です。反復回数は40回とします。
この関数を用いて作ったのは、次のようなプログラムです。
１つの実行例ですが、12個の素数が見つかり、最初に見つかったのは次に示す 308桁の素数でした。実行時間は Google Colaboratry の環境で約 30秒です。
何回か実行してみると、素数の桁数はほとんどが 309桁で、一部が 308桁です。これは \(\mr{log}_{10}2^{1023}\fallingdotseq307.95\) なので、そうなるはずです。また、１万個の n のうちの素数の数は 8～18 個程度となりました。実行結果について「素数定理」と「反復回数」の観点から考察します。
素数定理
数学では、\(x\) 以下の素数の個数を \(\pi(x)\) で表わします。素数定理によると、
\(\pi(x)\sim\dfrac{x}{\mr{log}(x)}\)
です。左辺と右辺をつなぐ \(\sim\) は、
左辺と右辺の比率 \(\longrightarrow\:1\:\:(x\longrightarrow\infty)\)
を意味します。以下、
\(\pi(x)=\dfrac{x}{\mr{log}(x)}\)
と考えて、m ビットの数に含まれる素数の割合を見積もります。m ビットの数の総数は \(2^{m-1}\) 個なので、m ビット数の素数割合は、
ですが、\(\dfrac{m-2}{m-1}\) を \(1\) と見なすと、簡潔に、
素数割合 \(=\dfrac{1}{\mr{log}2\cdot m}\)
です。この式に \(m=1024\) を代入すると、
素数割合 \(\fallingdotseq0.0014\)
となります。つまり、
と言えます。これは上の実験で、１万個の n のうちの素数の数は 8～18 個程度だったことに合致します。
反復回数
プログラムを少々変更して、
何回目の反復（iteration）で素数\(\cdot\)合成数の判定ができたか
を調べると、素数判定のときは当然 iteration = 40 ですが、
合成数判定のときの iteration = 1
であることが分かります（１万個の素数判定をする前提です）。つまり、\(n\) が合成数なら最初の計算で即、合成数と判明します。何回かの反復の後に合成数と判明することは、上の計算では無いのです。
この理由は、\(n\) が合成数だと「\(a\:(1\leq a\leq n-1)\) のなかで Miller-Rabin の条件を満たす底 \(a\) の比率は \(\tfrac{1}{4}\) 以下」という定理の \(\tfrac{1}{4}\) が（一般には）過大評価であることによります。たとえば、\(n\) が２つの異なる素数の積の場合、
\(\begin{eqnarray}
&&\:\:n&=p_1p_2\\
&&\:\:n-1&=2^ek\\
&&\:\:p_1-1&=2^{e_1}k_1\\
&&\:\:p_2-1&=2^{e_2}k_2\\
\end{eqnarray}\)
（\(e,e_1,e_2\geq1,\:\:k,k_1,k_2\) は奇数）
において \(\tfrac{1}{4}\) 以下の主な根拠は、
\(\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\leq k_1k_2\)
でした。ところが、この式で等号が成り立つのは、特に \(n\) が巨大だと、めったにありません。高々 10,000個程度の合成数を判定したとしても、Miller-Rabin の条件を満たす底 \(a\) が現れる確率はほとんどゼロに等しいのです。
ランダムに選んだ数 \(n\) のほとんどは（1024 ビットの数の場合 99.86 % は）合成数です。したがって「合成数を合成数だと速く判定する」のが素数判定アルゴリズムのポイントであり、反復回数をどうするかは全体の速度にそれほど関係ありません。このあたりの事情はフェルマの条件で素数判定をしても同じです。
ただし、フェルマの条件とは違って、ランダムに選んだ底 \(a\) が Miller-Rabin の条件を満たす確率が、\(n\) の値にかかわらず必ず \(\tfrac{1}{4}\) 以下であることが数学的に保証されています。そこが Miller-Rabin の素数判定アルゴリズムの価値なのでした。
今まで「高校数学で理解する・・・」という記事を何回か書きましたが、その中に暗号についての一連の記事があります。
No.310「高校数学で理解するRSA暗号の数理（１）」
No.311「高校数学で理解するRSA暗号の数理（２）」
No.313「高校数学で理解する公開鍵暗号の数理」
No.315「高校数学で理解する楕円曲線暗号の数理（１）」
No.316「高校数学で理解する楕円曲線暗号の数理（２）」
の５つです。これらは公開鍵暗号と、その中でも代表的な RSA暗号、楕円曲線暗号の数学的背景を書いたものです。情報通信をインフラとする現代社会は、この公開鍵暗号がなくては成り立ちません。"数学の社会応用" の典型的な例と言えるでしょう。
これらの暗号では、10進数で数10桁～数100桁の素数が必要です。ないしは、数10桁～数100桁の数が素数かどうかを判定する必要があります。
たとえば、マイナンバー・カードの認証に使われている RSA暗号の公開鍵は 2048ビットで、1024ビットの素数２つを掛け合わせて個人ごとに作られます。1024ビットということは \(2^{1023}\) ～ \(2^{1024}-1\) の数であり、10進では約300桁の巨大数です。素数を生成する式はないので、作るためには1024ビットの数をランダムに選び、それが素数かどうかを実用的な時間で判定する必要があります。
ビットコインのデジタル署名で使われているのは、256ビットの楕円曲線暗号です。この暗号の公開鍵は一般に公開されていますが（暗号の仕組みから個人ごとに作る必要はない）、この公開鍵を設計するときに必要なのは、256ビット＝約80桁（10進）の数が素数かどうかを判定することです。
つまり、公開鍵暗号の基礎となっている技術が「素数判定」なのです。そこで今回は、素数判定の方法で一般的な「Miller-Rabin テスト」の数学的背景を書きます。Miller、Rabin は、このテストを考案した数学者２人の名前です。
前提知識
本論に入る前に前提知識について整理します。「高校数学で理解する・・・」というタイトルは「高校までで習う数学の知識だけを前提とする」という意味です。従って、その前提からはずれるものはすべて証明するのが基本方針です。
今回は、以前の「高校数学で理解する・・・」で証明した事項を前提知識とします。
・合同式
・フェルマの小定理
・中国剰余定理
・オイラー関数
・群
です。また、暗号の記事ではありませんが、No.355「高校数学で理解するガロア理論（２）」の次の事項も前提とします。
・剰余群
・既約剰余類群
・巡回群
・群の直積
・群の同型
以下、剰余群以下の事項について、素数判定に関わるところを簡単に復習します。
剰余群
整数の集合を \(Z\) で表し、整数 \(n\) の倍数の集合を \(nZ\) とします。また、
\(\ol{j_n}\)
は、\(\bs{n}\) で割った余りが \(\bs{j}\) である整数の集合とします（剰余類と呼ばれる）。たとえば、\(n=9,\:j=2\) とすると、\(\ol{2_9}\) は「\(9\) で割ったら \(2\) 余る整数の集合」で、
\(\ol{2_9}=\{\:\cd,\:-16,\:-7,\:2,\:11,\:20,\:29,\:\cd\:\}\)
です。剰余群 \(Z/nZ\) とは、
\(Z/nZ=\{\ol{0_n},\:\ol{1_n},\:\cd\:,\:\ol{(n-1)_n}\}\)
で示される「無限集合を元とする有限集合」です。\(n=9\) だと、
\(Z/9Z=\{\ol{0_9},\:\ol{1_9},\:\ol{2_9},\:\ol{3_9},\:\ol{4_9},\:\ol{5_9},\:\ol{6_9},\:\ol{7_9},\:\ol{8_9}\}\)
です。この集合の元の加算 \(+\) を、
\(\ol{i_n}+\ol{j_n}=\ol{(i+j)_n}\)
と定義すると（右辺は整数のたし算）、\(Z/nZ\) はこの演算について群の定義を満たし（＝加法群）、この群を剰余群と呼びます。一般に有限群 \(G\) の元の数＝群位数を \(|G|\) で表しますが、剰余群の群位数は、
\(|Z/nZ|=n\)
です。以降、剰余類と整数を同一視して、
\(Z/9Z=\{0,\:1,\:2,\:3,\:4,\:5,\:6,\:7,\:8\}\)
というように書きます。従って、\(1\) は 整数の \(1\) を表すことも、また、\(Z/nZ\) の元（＝ \(n\) で割ると \(1\) 余る数の集合＝ \(\ol{1_n}\)）を表すこともあります。どちらかは文脈で決まります。
既約剰余類群
\(Z/nZ\) の元 \(\{0,\:1,\:\cd\:,\:j,\:\cd\:,\:n-1\}\) から \(\mr{gcd}(j,\:n)=1\) となる元（＝ \(n\) と素な元）だけを取り出した集合を既約剰余類群といい、\((Z/nZ)^{*}\) で表します。例をあげると、
\(\begin{eqnarray}
&&\:\:(Z/9Z)^{*}&=\{\ol{1_9},\:\ol{2_9},\:\ol{4_9},\:\ol{5_9},\:\ol{7_9},\:\ol{8_9}\}\\
&&&=\{\:1,\:2,\:4,\:5,\:7,\:8\:\}\\
\end{eqnarray}\)
です。この集合の、元と元との乗算 \(\cdot\) を、
\(\ol{i_n}\cdot\ol{j_n}=\ol{(ij)_n}\)
で定義すると（右辺の \(ij\) は整数の乗算）、\((Z/nZ)^{*}\) は乗算を演算とする群になります（＝乗法群）。従って、任意の元 \(a\in(Z/nZ)^{*}\) の逆元 \(a^{-1}\) が存在して、
\(a\cdot a^{-1}=1\)
が成り立ちます。つまり乗算と除算が自由にできます。\((Z/9Z)^{*}\) の例では、
\(\begin{eqnarray}
&&\:\:1^{-1}&=1&&\\
&&\:\:2^{-1}&=5, &5^{-1}&=2\\
&&\:\:4^{-1}&=7, &7^{-1}&=4\\
&&\:\:8^{-1}&=8&&\\
\end{eqnarray}\)
です。\((Z/nZ)^{*}\) の群位数は、オイラー関数 \(\varphi\) を使って、
\((Z/nZ)^{*}=\varphi(n)\)
で表されます。\(\varphi(n)\) は「\(n\) 以下で \(n\) とは互いに素な数の個数」です。\(p,\:q\) を異なる素数とすると、
\(\begin{eqnarray}
&&\:\:\varphi(p)&=p-1\\
&&\:\:\varphi(pq)&=(p-1)(q-1)\\
&&\:\:\varphi(p^2)&=p(p-1)\\
\end{eqnarray}\)
などが成り立ちます。
巡回群
\(p\) を奇素数（\(p\neq2\)）とすると、既約剰余類群 \((Z/pZ)^{*}\) は生成元 \(g\) をもちます。つまり、
\((Z/pZ)^{*}=\{\:g,\:g^2,\:g^,\:\cd\:,\:g^{p-1}=1\:\}\)
と表され、群位数は \(\varphi(p)=p-1\) です。このように、一つの生成元の累乗で全ての元が表せる群を巡回群と言います（\(1\) の次は再び \(g\) になって巡回する）。また、\(n\) が \(p\) の累乗、\(n=p^{\al}\:(\al\geq2)\) のときも \((Z/p^{\al}Z)^{*}\) は生成元をもつ巡回群です。\(\al=2\) のときの群位数は、
\(|(Z/p^2Z)^{*}|=\varphi(p^2)=p(p-1)\)
です。\((Z/9Z)^{*}\) の場合、群位数は \(\varphi(9)=6\) で、\(g=2\) と \(g=5\) が生成元になり、
\(\begin{eqnarray}
&&\:\:(Z/9Z)^{*}&=\{2,\:2^2=4,\:2^3=8,\:2^4=7,\:2^5=5,\:2^6=1\}\\
&&&=\{5,\:5^2=7,\:5^3=8,\:5^4=4,\:5^5=2,\:5^6=1\}\\
\end{eqnarray}\)
などと表せます。\(1,\:4,\:7,\:8\) は生成元ではありません。
群の直積、群の同型
\(G\) と \(H\) を有限群とし、その元を \(g_i\in G,\:h_j\in H\) として、２つの元のペア、
\((g_i,\:h_j)\) \((1\leq i\leq|G|,\:1\leq j\leq|H|)\)
を作るとき、すべてのペアを元とする集合を「群の直積」と言い、\(G\times H\) で表します。元と元の演算を \(g_i\) と \(h_i\) で個別に行うことで、直積も群になります。その群位数は、
\(|G\times H|=|G|\cdot|H|\)
です。
中国剰余定理によると、\(m,\:n\) が互いに素のとき、
\(x\equiv a\:\:(\mr{mod}\:m)\)
\(x\equiv b\:\:(\mr{mod}\:n)\)
の連立合同方程式は、\(mn\) を法として唯一の解を持ちます。\(x\) を \(m\) で割った余りを \(x_m\)、\(n\) で割った余りを \(x_n\) とし、
\(f\::\:x\:\longrightarrow\:(x_m,\:x_n)\)
の写像 \(f\) を定義すると、中国剰余定理によって \(f\) は１対１写像であり、かつ、
\(\begin{eqnarray}
&&\:\:f(xy)&=((xy)_m,\:\:(xy)_n)\\
&&&=((x_m\cdot y_m)_m,\:\:(x_n\cdot y_n)_n)\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:f(x)f(y)&=(x_m,\:x_n)\:(y_m,\:y_n)\\
&&&=((x_m\cdot y_m)_m,\:\:(x_n\cdot y_n)_n)\\
\end{eqnarray}\)
なので、
\(f(xy)=f(x)f(y)\)
が成り立ちます。また同様に \(f(x+y)=f(x)+f(y)\) であり、\(f\) は演算を保存する同型写像です。従って、剰余群 \(Z/mnZ\) は、２つの群の直積との間で "群の同型" が成り立ち、
\(Z/mnZ\cong Z/mZ\times Z/nZ\)
です（＝中国剰余定理の群による表現）。また 既約剰余類群 \((Z/mnZ)^{*}\) は、
\((Z/mnZ)^{*}\cong(Z/mZ)^{*}\times(Z/nZ)^{*}\)
と直積で表現できます。\(m,\:n\) がともに奇素数で \(m=p,\:n=q\:(\neq p)\)だと、
\((Z/pqZ)^{*}\cong(Z/pZ)^{*}\times(Z/qZ)^{*}\)
です。\((Z/pqZ)^{*}\) は巡回群でありませんが、２つの巡回群の直積で表現できることになります。
以上を前提として「Miller-Rabin テスト」のことを書きますが、これは「確率的素数判定アルゴリズム」の一種です。
| 確率的素数判定アルゴリズム |
「Miller-Rabin テスト」は「フェルマ・テスト」の発展形と言えるものです。そこでまず、「フェルマ・テスト」の原理になっている「フェルマの小定理」から始めます。
フェルマの小定理
素数がもつ重要な性質を示したのが、フェルマの小定理です。
フェルマの小定理 \(p\) を素数とすると、\(p\) と素な \(a\) について、 \(a^{p-1}\equiv1\:\:(\mr{mod}\:p)\) が成り立つ。 |
この定理の \(a\) を、指数関数の「底（base）」と呼びます。偶数の素数は \(2\) しかないので、以降、\(\bs{n}\) は \(\bs{3}\) 以上の奇数として素数判定を考えます。フェルマの小定理を素数判定用に少々言い換えると、次のように表現できます。
フェルマの小定理 \(n\) を \(3\) 以上の奇数とする。\(\bs{n}\) が素数であれば、\(\bs{1\leq a\leq n-1}\) であるすべての \(\bs{a}\) について、次の "フェルマの条件" が成り立つ。 フェルマの条件 \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) |
このフェルマの小定理の対偶は次のようになります。
フェルマの小定理の対偶 \(n\) が \(3\) 以上の奇数であるとき、\(\bs{1\leq a\leq n-1}\) であるどれか一つの \(\bs{a}\) について、 \(a^{n-1}\not\equiv1\:\:(\mr{mod}\:n)\) であれば（＝フェルマの条件に反すれば）\(\bs{n}\) は合成数である。 |
\(n\) が \(3\) 以上の奇数の合成数のとき、\(1\leq a\leq n-1\) について、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\)
\(a^{n-1}\not\equiv1\:\:(\mr{mod}\:n)\)
のどちらになるのか、\(a\) ごとに検討してみます。もちろん \(a=1\) なら \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) です。また、\(a=n-1\:(=-1)\) でも、\(n-1\) が偶数なので、 \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) です。
また、\(a\) が \(n\) と互いに素でないとき、つまり \(\mr{gcd}(n,\:a)\neq1\) ときは \(a^{n-1}\not\equiv1\:\:(\mr{mod}\:n)\) です。なぜなら、\(a\) と \(n\) の最大公約数を \(d\:(\neq1)\) として、もし \(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) だとすると、
\(a^{n-1}=k\cdot n+1\:\:(k\) は整数\()\)
と表わせますが、
左辺について \(d\mid a^{n-1}\)
右辺について \(d\nmid(k\cdot n+1)\)
となってしまい、矛盾するからです。
\(a\neq1,\:n-1\)、 \(\mr{gcd}(n,\:a)=1\) のときにどうなるかは、\(a\) によって両方がありえます。ためにしに、\(n=21\) で計算してみると、
| \(1\) | \(1\) |
| \(2\) | \(4\) |
| \(3\) | \(9\) |
| \(4\) | \(16\) |
| \(5\) | \(4\) |
| \(6\) | \(15\) |
| \(7\) | \(7\) |
| \(8\) | \(1\) |
| \(9\) | \(18\) |
| \(10\) | \(16\) |
| \(11\) | \(16\) |
| \(12\) | \(18\) |
| \(13\) | \(1\) |
| \(14\) | \(7\) |
| \(15\) | \(15\) |
| \(16\) | \(4\) |
| \(17\) | \(16\) |
| \(18\) | \(9\) |
| \(19\) | \(4\) |
| \(20\) | \(1\) |
となります。色を塗った10個が \(a\neq1,\:n-1\)、 \(\mr{gcd}(n,\:a)=1\) のところですが、\(\equiv1\) \((a=8,\:13)\) と \(\not\equiv1\)（それ以外の8個）があることがわかります。とにかく、上の表で一つでも \(\bs{\not\equiv1}\) があれば、\(n\) は合成数だと判断できます。
このフェルマの小定理の対偶を利用して、巨大整数（数10桁～数100桁） \(n\) が素数かどうかを確率的に判定できます。つまり、\(1\leq a\leq n-1\) である数をランダムに、順々に選び、ある \(a\) がフェルマの条件に反すれば、その時点で \(n\) は合成数と判定します。何回か試行してすべての \(a\) がフェルマの条件に合致するなら（＝合成数だと判定できなければ）、\(n\) は素数の可能性が高い。
しかし困ったことに「合成数でありながら、多数の \(\bs{a}\) でフェルマの条件を満たしてしまう \(\bs{n}\)」が存在します。"カーマイケル数" です。最小のカーマイケル数は \(561=3\cdot11\cdot17\) ですが、\(\mr{gcd}(561,\:a)=1\) であるすべての \(a\:\:(1\leq a\leq560)\) で、
\(a^{560}\equiv1\:\:(\mr{mod}\:561)\)
が成り立ちます。その理由ですが、\(a\) を \(3,\:11,\:17\) のすべてと素な任意の数（＝ \(561\) と素な任意の数）とすると、フェルマの小定理より、
\(\begin{eqnarray}
&&\:\:a^{2}&\equiv1\:\:(\mr{mod}\:3)\\
&&\:\:a^{10}&\equiv1\:\:(\mr{mod}\:11)\\
&&\:\:a^{16}&\equiv1\:\:(\mr{mod}\:17)\\
\end{eqnarray}\)
が成り立ちます。\(560\) は、\(2,\:10,\:16\) 全部の倍数なので、それぞれの合同式の両辺を適切に累乗すると、
\(a^{560}\equiv1\:\:(\mr{mod}\:3)\)
\(a^{560}\equiv1\:\:(\mr{mod}\:11)\)
\(a^{560}\equiv1\:\:(\mr{mod}\:17)\)
が成り立つ。そうすると、中国剰余定理により、
\(a^{560}\equiv1\:\:(\mr{mod}\:3\cdot11\cdot17)\)
が成り立ちます。\(560\) 以下で \(561\) と素な数の個数は、オイラー関数 \(\varphi(n)\)（＝ \(n\) 以下で \(n\) と素な数の個数）を使うと、
\(\begin{eqnarray}
&&\:\:\varphi(561)&=\varphi(3)\varphi(11)\varphi(17)\\
&&&=2\cdot10\cdot16=320\\
\end{eqnarray}\)
なので、\(\dfrac{320}{560}=\dfrac{4}{7}\)、つまり半数以上の \(a\) でフェルマの条件が満たされることになります。これを一般的に言うと、カーマイケル数 \(c\) が３個の素数 \(p,\:q,\:r\) の積の場合、
\(\begin{eqnarray}
&&\:\:c&=pqr\\
&&\:\:\varphi(c)&=(p-1)(q-1)(r-1)\\
\end{eqnarray}\)
なので、この２つの比は、\(p,\:q,\:r\) が大きくなると \(1\) に近づきます。それは、ほとんど全ての \(a\:\:(1\leq a\leq c-1)\) がフェルマの条件を満たすことを意味します。
カーマイケル数は、特に \(n\) が巨大だと極めて希です。Wikipedia によると、「\(1\) から \(10^{21}\) の間には \(20,138,200\) 個のカーマイケル数があり、これはおよそ \(5\cdot10^{13}\) 個にひとつの割合」だそうです。しかし、カーマイケル数が無限個あることも証明されています。\(n\) が "運悪く" カーマイケル数だと、フェルマ\(\cdot\)テストでは素数と判定されてしまう。つまり、フェルマの条件を使って素数を確率的に判定するアルゴリズムには問題があるわけです。
Miller-Rabin の条件
そこで、素数の条件として、フェルマの条件とは別のものを考えます。フェルマの条件、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\)
において、\(n\) が素数とすると、\(n-1\) は偶数です。そこで、
\(n-1=2^ek\) （\(e\geq1,\:k\) は奇数）
と表します。この表記を用いて、\(a^{n-1}-1\) という式を因数分解すると、
\(\begin{eqnarray}
&&\:\:a^{n-1}-1&=a^{2^ek}-1\\
&&&=(a^{2^{e-1}k})^2-1\\
&&&=(a^{2^{e-1}k}+1)(a^{2^{e-1}k}-1)\\
&&&=(a^{2^{e-1}k}+1)((a^{2^{e-2}k})^2-1)\\
&&&=(a^{2^{e-1}k}+1)(a^{2^{e-2}k}+1)(a^{2^{e-2}k}-1)\\
&&& \vdots\\
\end{eqnarray}\)
と続きます。結局、因数分解は、
| \(a^{n-1}-1=\) | \((a^{2^{e-1}k}\) | \(+1)\cdot\) | ||
| \((a^{2^{e-2}k}\) | \(+1)\cdot\) | |||
| \((a^{2^{e-3}k}\) | \(+1)\cdot\) | |||
| \(\vdots\) | ||||
| \((a^{2^2k}\) | \(+1)\cdot\) | |||
| \((a^{2k}\) | \(+1)\cdot\) | |||
| \((a^k\) | \(+1)\cdot(a^k-1)\) | \((\br{A})\) |
となります。これを \((\br{A})\) 式とします。\(n\) が素数のときは、フェルマの条件を変形すると、
\(a^{n-1}-1\equiv0\:\:(\mr{mod}\:n)\)
なので、フェルマの条件と等価な式は、
\((\br{A})\) 式の右辺 \(\equiv0\:\:(\mr{mod}\:n)\)
であり、ということは、
\((\br{A})\) 式の右辺の少なくとも１つの項 \(\equiv0\:\:(\mr{mod}\:n)\) |
が成立します。\(\bs{n}\) が素数であるのがポイントです。\(n\) が合成数ならこんなことは言えません。このことより、\(n\) が素数であるための新たな条件が導けます。次項です。
素数の条件（Miller-Rabin）
\(n\) を \(3\) 以上の奇数とし、 \(n-1=2^ek\) （\(e\geq1,\:k\) は奇数） と表されているものとする。このとき、\(\bs{n}\) が素数であれば、\(\bs{1\leq a\leq n-1}\) であるすべての \(\bs{a}\) について、次の Miller-Rabin の条件が成り立つ。 Miller-Rabin の条件 （１） \(a^k\equiv1\:\:(\mr{mod}\:n)\) もしくは （２） ある \(r\:(0\leq r\leq e-1)\) について、 \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) |
\(a^{2^ik}\:\:(0\leq i\leq e-1)\) の \(e\) 個の数列を Miller-Rabin 系列と呼ぶことにします。
\(a^k,\:a^{2k},\:a^{4k},\:\cd\:,\:a^{2^{e-1}k}\)
です。この系列は、ある項の２乗が次の項になっています。従って \(\mr{mod}\:n\) でみて \(a^{2^rk}\equiv-1\) になれば、以降の項はすべて \(\equiv1\:(\mr{mod}\:n)\) になります。ということは、系列の中で \(\equiv-1\) となる項は「全く無い」か「一つだけある」のどちらかです。
ちなみに、Miller-Rabin による素数の条件の対偶は次の通りです。これを利用して合成数の判定ができます。
合成数の判定（対偶） \(n\) を \(3\) 以上の奇数とし、 \(n-1=2^ek\) （\(e\geq1,\:k\) は奇数） と表されているものとする。このとき、\(\bs{1\leq a\leq n-1}\) のある \(\bs{a}\) について、 （１） \(a^k\not\equiv1\:\:(\mr{mod}\:n)\) かつ （２） すべての \(r\:(0\leq r\leq e-1)\) について、 \(a^{2^rk}\not\equiv-1\:\:(\mr{mod}\:n)\) が成り立てば、\(n\) は合成数である。 |
\(\bs{n}\) が素数であれば、フェルマーの条件と Miller-Rabin の条件は等価です。しかし、\(n\) が合成数のときは、フェルマの条件と Miller-Rabin の条件の意味が違ってきます。それが次です。
\(n\) が合成数のとき
\(n\) が合成数のときは、フェルマの条件から Miller-Rabin の条件を導くことはできません。なぜなら「\(n\)が素数」が導出のキーだからです。つまり、
| フェルマの条件を満たす底 \(a\) の集合を \(F\) | |
| Miller-Rabin の条件を満たす底 \(a\) の集合を \(M\) |
とすると、\(a\in F\) であっても \(a\in M\) とは限らない。しかし、\((\br{A})\) 式でわかるように \(a\in M\) なら必ず \(a\in F\) です。従って、
\(M\:\subset\:F\)
です。ということは、数 \(a\) についてのフェルマーの条件によって \(n\) が合成数だと判定できなくても（つまり \(a\in F\)）、Miller-Rabin の条件で合成数と判定できる（つまり \(a\notin M\)）可能性があることになります。つまり合成数の判定においては、Miller-Rabin の条件はフェルマーの条件より厳格です。
しかも Miller-Rabin の条件は、合成数を合成数だと判定できる確率（ないしは判定できない確率）が、\(\bs{n}\) の値にかかわらず示せるのです。それが次の定理です。
Miller-Rabin の定理
Miller-Rabin の定理 \(n\) を \(3\) 以上の奇数の合成数とする。また、\(n-1=2^ek\:\:(e\geq1,\:k\) は奇数\()\) と表されているものとする。このとき、 Miller-Rabin の条件 （１） \(a^k\equiv1\:\:(\mr{mod}\:n)\) もしくは （２） ある \(r\:(0\leq r\leq e-1)\) について、 \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) を満たす底 \(a\:(1\leq a\leq n-1)\) は、\(\bs{n-1}\) 個のうちの \(\bs{1/4}\) 以下である。 |
\(\bs{n}\) がいかなる数であっても成り立つのがポイントです。実際に計算をしてみます。\(n\) を \(9\leq n < 10000\) である奇数の合成数とします。調べてみると、その総数は \(3771\)個です。そして、
\(L=\)Miller-Rabin の条件を満たす底 \(a\) の個数
\(P=\dfrac{L}{n-1}\)
\(P=\dfrac{L}{n-1}\)
とし、\(3771\)個の \(n\) のうち \(P\geq0.2\) のものをリストアップすると、次の５つだけです。
| \(9\) | \(3\) | \(1\) | \(2\) | \(0.25\) |
| \(91\) | \(1\) | \(45\) | \(18\) | \(0.20\) |
| \(703\) | \(1\) | \(351\) | \(162\) | \(0.23\) |
| \(1891\) | \(1\) | \(945\) | \(450\) | \(0.24\) |
| \(8911\) | \(1\) | \(4455\) | \(1782\) | \(0.20\) |
\(n=9\) のとき、\(P\) は最大値の \(0.25\) です。それ以降、\(n=1891\) のときに \(P\fallingdotseq0.24\) となりますが、\(0.25\) を越える \(n\) は（ \(9\leq n < 10000\) では）無いことがわかります。そしてこの定理は、\(\bs{n}\) がいかなる奇数の合成数であっても \(\bs{P\leq0.25}\) と主張しているわけです。
これでまず言えることは、Miller-Rabin の条件にとっての「カーマイケル数のような数」はあり得ないことです。
さらにこの定理によって、素数判定の信頼度を示すことができます。比喩で言うと次のとおりです。
| 正方形の、中が見えない箱があり、玉が \(100\)個入っています。箱は「素数箱」と「合成数箱」の区別がありますが、そのどちらかは見た目で判別できません。ただし、素数箱なら\(100\)個の白玉が入っていて、合成数箱なら \(25\)個の白玉と \(75\)個の赤玉が入っています。 | |
| 箱の上面には穴があって、そこから手を入れて玉を取り出し、色を確認した後、玉を箱に戻す（そしてかき混ぜる）ことができます。この確認は繰り返しができて、その繰り返しで、箱が素数箱か合成数箱かを判断します。 | |
| 最初に取り出した玉が赤玉なら、箱は合成数箱だとわかります。しかし白玉だと、素数箱の可能性が高いものの、断言はできない。合成数箱でも白玉を取り出す確率が \(1/4\) あるからです。従って２回目の確認をします。 | |
| ２回続けて白だと、素数箱である可能性がぐんと高まります。もしそれが合成数箱だとすると、２回続けて白の確率は \(1/16\) しかないからです。もちろん２回目が赤だと合成数箱です。 | |
| このようにして、赤が出ればその時点で合成数箱と判断し、白が出続ければ確認を繰り返します。もし合成数箱だとすると、白が５回出続ける確率は \(1/1024\) であり、以降、どんどん減っていくので、ある回数で打ち切って素数箱と判断します。 |
以上の考え方で \(n\) の素数判定をするアルゴリズムが次です。
Miller-Rabin の素数判定アルゴリズム
|
\(r=40\) だとすると、Miller-Rabin の素数判定アルゴリズムで「素数と判定したにもかかわらず実は合成数」の確率は、
\(\dfrac{1}{4^{40}}\) 以下
であることが保証されます。\(4^{40}\) は、\(\fallingdotseq\:1.2\times10^{24}\) で、\(10\)進数で\(25\)桁の数です。あまりに巨大すぎて想像するのは難しいのですが、たとえば、１秒の \(100\)万分の \(1\) の時間は \(1\) マイクロ秒で、\(1\) 秒間に地球を \(7.5\)周する光が \(300\)メートルしか進まない時間です。一方、宇宙の年齢は \(138\)億年程度と言われています。この宇宙の年齢をマイクロ秒で表すと、\(4.4\times10^{23}\) マイクロ秒です。ということは、\(4^{40}\) はその３倍近い数字です。
\(\dfrac{1}{4^{40}}\) は、数学的には \(0\) ではありませんが、確率としては実用的に \(0\) です。以上が Miller-Rabin の素数判定の原理です。
以降、 なぜ \(\dfrac{1}{4}\) 以下であると言えるのか、その証明をします。
| Miller-Rabin の定理の証明 |
定理を再度述べると次の通りです。
Miller-Rabin の定理（再掲） \(n\) を \(3\) 以上の奇数の合成数とする。また、\(n-1=2^ek\:\:(e\geq1,\:k\) は奇数\()\) と表されているものとする。このとき、 Miller-Rabin の条件 （１） \(a^k\equiv1\:\:(\mr{mod}\:n)\) もしくは （２） ある \(r\:(0\leq r\leq e-1)\) について、 \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) を満たす \(a\:(1\leq a\leq n-1)\) は、\(n-1\) 個のうちの \(1/4\) 以下である。 |
３つのケースにわけて証明します。以降の証明は、後藤・鈴木（首都大学東京）「Miller-Rabin素数判定法における誤り確率の上限」を参考にしました。
| \(n=p^2t\:\:(p\)は奇素数。\(t\geq1\) は奇数\()\)と表されるとき
\(n\) が奇素数の２乗で割り切れるときです。このことを、\(n\) が「平方因子」をもつ、と言います。\(t\) の素因数分解に \(p\) が現れてもかまいません。平方因子が複数個ある場合は、そのどれかを \(p\) とします。
| |
| \(n=p_1\cdot p_2\:(p_1,\:p_2\) は奇素数で \(p_1\neq p_2)\) | |
| \(n=p_1\cdot p_2\cdot\cd\cdot p_m\:(m\geq3\) 個の相異なる奇素数の積\()\) |
② ③ のケースは \(n\) が平方因子を持たないので ① と排他的であり、また ② と ③ も排他的です。いずれの場合も \(n\) が奇数なので、素因数に \(2\) は現れません。以降の３つのケースに分けた証明では、\(p\) を素数としたとき既約剰余類群 \((Z/pZ)^{*}\) 、\((Z/p^2Z)^{*}\) が巡回群であることを利用します。
１． \(n=p^2t\:\:(\:p\)は奇素数。\(t\geq1\) は奇数\()\)
Miller-Rabin の条件を満たす \(a\:(0\leq a\leq n-1)\) の集合を \(M\) とします。上で説明したように、\(n\) が合成数であったとしても Miller-Rabin の条件が成立すればフェルマの条件も成立します（\(n\) が合成数だとその逆は成り立たない）。従って、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\)
が成り立ちます。このフェルマの条件を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(F\) とすると、\(M\:\subset\:F\) なので元の数は、
\(|M|\leq|F|\)
です。さらに、\(p^2\mid n\)（＝ \(p^2\) が \(n\) を割り切る）なので、
\(a^{n-1}\equiv1\:\:(\mr{mod}\:p^2)\)
\((\br{B})\)
も同時に成り立ちます。\((\br{B})\) 式を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(R_1\) とすると、\(a\in F\) なら \(a\in R_1\) なので、
\(\begin{eqnarray}
&&\:\:F&\subset R_1\\
&&\:\:|F|&\leq|R_1|\\
\end{eqnarray}\)
が成り立ちます。\(|M|\leq|F|\) とあわせると、
\(|M|\leq|R_1|\)
です。次に、剰余群 \(Z/p^2Z\) の元 で \((\br{B})\) 式を満たす \(a\:(0\leq a\leq p^2-1)\) の集合を \(R_2\) とします。\(x\in R_2\) だとすると、\(\mr{mod}\:p^2\) では、
\(\begin{eqnarray}
&&\:\:x&=x+p^2\\
&&&=x+2p^2\\
&&& \vdots\\
&&&=x+(t-1)p^2\leq p^2t-1\\
\end{eqnarray}\)
です。つまり、\((\br{B})\) 式を満たす \(Z/p^2Z\) の元１個に対して、\((\br{B})\) 式を満たす、\(0\leq a\leq n-1\:(p^2t-1)\) の \(t\)個の数が対応します。従って、
\(t|R_2|=|R_1|\)
です。\(|M|\leq|R_1|\) とあわせると、
\(|M|\leq t|R_2|\)
です。
剰余群 \(Z/p^2Z\) の元で \((\br{B})\) 式を満たすのは、\(p^2\) と互いに素な元だけです。つまり、既約剰余類群 \((Z/p^2Z)^{*}\) の元で \((\br{B})\) 式を満たすものの集合が \(R_2\) であるとも言えます。以降、 \((Z/p^2Z)^{*}\) を使って \(R_2\) の元の数、\(|R_2|\) を見積もります。それには \((Z/p^2Z)^{*}\) が巡回群であることを利用します。
一般に、巡回群においては次が成り立ちます。この定理を \((\br{C})\) とします。
巡回群 \(G\)（群位数 \(d\)）において、\(x^m=1\) を満たす \(x\) の個数は \(\mr{gcd}(m,\:d)\) 個である。
\((\br{C})\) |
【証明】
\(h=\mr{gcd}(m,\:d)\) とおく。位数 \(d\) の巡回群 \(G\) は、生成元 \(g\) を用いて、
\(G=\{g,\:g^2,\:g^3,\:\cd\:,\:g^{d-1},\:g^d=1\}\)
と表現できる。そこで \(x=g^i\:\:(1\leq i\leq d)\) と表すと、
\(\begin{eqnarray}
&&\:\:(g^i)^m&=1\\
&&\:\:g^{im}&=1\\
\end{eqnarray}\)
なので、\(im\) は群位数 \(d\) の整数倍である。つまり、
\(d\mid im\)
である。\(h=\mr{gcd}(m,\:d)\) として \(d\,'=\dfrac{d}{h}\) \(m\,'=\dfrac{m}{h}\) とおくと、
\(d\,'\mid im\,'\)
になるが、\(d\,'\) と \(m\,'\) は互いに素なので、
\(d\,'\mid i\)
である。つまり \(i\) は \(d\,'=\dfrac{d}{h}\) の倍数である。従って、\(1\leq i\leq d\) であることを考慮すると、
\(i=\dfrac{d}{h}\cdot j\:\:(1\leq j\leq h)\)
と表せる。つまり、\(x^m=1\) を満たす \(x\) の個数は \(h=\mr{gcd}(m,\:d)\) 個である。【証明終】
既約剰余類群 \((Z/p^2Z)^{*}\) は巡回群であり、群位数は\(\varphi(p^2)=p(p-1)\) です。従って、\((Z/p^2Z)^{*}\) の元で \(a^{n-1}=1\) を満たす元の数（\(=|R_2|\)）は定理 \((\br{C})\) により、
\(\begin{eqnarray}
&&\:\:|R_2|&=\mr{gcd}(p(p-1),\:n-1)\\
&&&=\mr{gcd}(p(p-1),\:p^2t-1)\\
\end{eqnarray}\)
となります。ここで、\(p^2t-1\) は \(p\) で割り切れないので、
\(\mr{gcd}(p(p-1),\:p^2t-1)=\mr{gcd}(p-1,\:p^2t-1)\)
ですが、この式の右辺は \(p-1\) 以下です。従って、
\(|R_2|\leq p-1\)
です。\(|M|\leq t|R_2|\) とあわせると、
\(|M|\leq t(p-1)\)
が得られました。従って、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&\leq\dfrac{t(p-1)}{tp^2-1}\\
&&&=\dfrac{p-1}{p^2-\dfrac{1}{t}}\\
\end{eqnarray}\)
となります。定義によって \(t\geq1,\:p\geq3\) ですが、上式の右辺は \(t\) についても \(p\) についても単調減少です。従って右辺の最大値は \(t=1,\:p=3\) のときで、
\(\dfrac{t(p-1)}{tp^2-1}\leq\dfrac{1}{4}\)
です。結論として、
\(\dfrac{|M|}{n-1}\leq\dfrac{1}{4}\)
となり、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は \(\dfrac{1}{4}\) 未満であることが証明されました。
ちなみに、この証明はフェルマの条件しか使っていません。つまり、
\(n\) が平方因子をもつなら、\(1\leq a\leq n-1\) のなかでフェルマの条件を満たす数の比率は \(\tfrac{1}{4}\) 未満
と言えます。ということは、平方因子をもつ数はカーマイケル数にはなりえないことが分かります。
２． \(n=p_1\cdot p_2\:(\:p_1,\:p_2\) は奇素数で \(p_1\neq p_2\:)\)
Miller-Rabin の定理を再掲します。
Miller-Rabin の定理（再掲） \(n\) を \(3\) 以上の奇数の合成数とする。また、\(n-1=2^ek\:\:(e\geq1,\:k\) は奇数\()\) と表されているものとする。このとき、 Miller-Rabin の条件 （１） \(a^k\equiv1\:\:(\mr{mod}\:n)\) もしくは （２） ある \(r\:(0\leq r\leq e-1)\) について、 \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) を満たす \(a\:(1\leq a\leq n-1)\) は、\(n-1\) 個のうちの \(1/4\) 以下である。 |
証明のポイントは２つあります。（２） の条件に関する Miller-Rabin 系列、
\(a^k,\:a^{2k},\:\:a^{4k},\:\cd\:,\:a^{(e-1)k}\)
を考えると、ある項の２乗が次の項なので、\(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) となる項があれば、それ以降の項は全て \(\equiv1\) となります。つまり、\(a^{2^rk}\equiv-1\) となる項は１つしかありません。従って、\(r\) を一つ決めたときに \(a^{2^rk}\equiv-1\) を満たす \(a\) の集合を \(A_2(r)\) とし、（２） を満たすすべての \(a\) の集合を \(A_2\) とすると、
\(|A_2|=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\)
が成り立ちます。さらに （１） の条件を満たす \(a\) の集合を \(A_1\) とすると、（１） と （２） は排他的です。従って、Miller-Rabin の条件を満たす \(a\) の集合を \(M\) とすると、
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&=|A_1|+\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\\
\end{eqnarray}\)
です。このことを以下の証明で利用します。もう一つの証明のポイントは、「１．\(\bs{n=p^2t\:\:(\:p}\) は奇素数。\(\bs{t\geq1}\) は奇数\(\bs{)}\)」での証明と同じように、巡回群の性質を利用することです。
まず前提として、Miller-Rabin の条件を満たす \(a\:(0\leq a\leq n-1)\) は、フェルマの条件、\(a^{n-1}\equiv1\:\:(\mr{mod}\:n)\) も満たしますが、これが成り立つ \(a\) は \(n\) とは素です。従って、既約剰余類群 \((Z/nZ)^{*}\:=\:(Z/p_1p_2Z)^{*}\) の範囲で \(a\) の個数を検討します。
もちろん、\(p_1\neq p_2\) なので、既約剰余類群 \((Z/p_1p_2Z)^{*}\) は巡回群ではありません。しかし \(p_1,\:p_2\) が互いに素なので、\((Z/p_1p_2Z)^{*}\) は２つの既約剰余類群の直積と同型であり、
\((Z/p_1p_2Z)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\)
と表せます。つまり、\(a\in(Z/p_1p_2Z)^{*}\) とし、
\(a\) を \(p_1\) で割った余りを \(a_{p_1}\)
\(a\) を \(p_2\) で割った余りを \(a_{p_2}\)
と書くと、\(a_{p_1}\in(Z/p_1Z)^{*},\:\:a_{p_2}\in(Z/p_2Z)^{*}\) ですが、ここで、
\(f\::\:a\:\longrightarrow\:(a_{p_1},\:a_{p_2})\)
の写像を定義すると、この写像は１対１（全単射）で、同型写像であり、上の「直積と同型」の式が成り立ちます。同型写像は \(f(xy)=f(x)f(y)\) というように演算を保存するので、演算してから写像した結果と写像してから演算した結果は同じです。
また、この \((Z/p_1Z)^{*}\) と \((Z/p_2Z)^{*}\) は、\(p_1\) と \(p_2\) が素数なので、生成元をもつ巡回群です。それぞれの群位数は、
\(\begin{eqnarray}
&&\:\:|(Z/p_1p_2Z)^{*}|&=\varphi(p_1p_2)\\
&&&=(p_1-1)(p_2-1)\\
\end{eqnarray}\)
\(|(Z/p_1Z)^{*}|=\varphi(p_1)=p_1-1\)
\(|(Z/p_2Z)^{*}|=\varphi(p_2)=p_2-1\)
であり、
\(|(Z/p_1p_2Z)^{*}|=|(Z/p_1Z)^{*}|\cdot|(Z/p_2Z)^{*}|\)
が成り立ちます。ここで \((Z/p_1Z)^{*}\) の任意の部分集合を \(H_1\)、\((Z/p_2Z)^{*}\) の任意の部分集合を \(H_2\) とします。
\(H_1\subset(Z/p_1Z)^{*}\)
\(H_2\subset(Z/p_2Z)^{*}\)
です。\((Z/p_1p_2Z)^{*}\) の元 \(a\) で、
\(a_{p_1}\in H_1\)
\(a_{p_2}\in H_2\)
となる \(a\) を考え、このような \(a\) の集合を \(H\) と書くと、
\(f\::\:a\:\longrightarrow\:(a_{p_1},\:\:a_{p_2})\)
の写像は１対１対応であり（＝中国剰余定理）、集合の元の数については、
\(|H|=|H_1|\cdot|H_2|\)
が成り立ちます。
以上を踏まえて証明に進みます。一般に、
\(x\equiv y\:\:(\mr{mod}\:p_1p_2)\) なら
\(x\equiv y\:\:(\mr{mod}\:p_1)\) かつ \(x\equiv y\:\:(\mr{mod}\:p_2)\)
が言えます。また、\(p_1\) と \(p_2\) は互いに素なので、
\(x\equiv y\:\:(\mr{mod}\:p_1)\) かつ \(x\equiv y\:\:(\mr{mod}\:p_2)\) なら
\(x\equiv y\:\:(\mr{mod}\:p_1p_2)\)
も言えます。なぜなら、\(p_1\mid(x-y)\) かつ \(p_2\mid(x-y)\) なら、\(p_1p_2\mid(x-y)\) だからです。つまり、
\(x\equiv y\:\:(\mr{mod}\:p_1p_2)\)
\(x\equiv y\:\:(\mr{mod}\:p_1)\) かつ \(x\equiv y\:\:(\mr{mod}\:p_2)\)
の２つは、\(p_1,\:p_2\) が素数という前提では等価です。従って、Miller-Rabin の条件は次のように言い換えることができます。
\(n=p_1p_2,\:\:n-1=2^ek\) とするとき、 Miller-Rabin の条件（言い換え） （１） (1a) \(a^k\equiv1\:\:(\mr{mod}\:p_1)\) かつ (1b) \(a^k\equiv1\:\:(\mr{mod}\:p_2)\) もしくは、 （２） ある \(r\:(0\leq r\leq e-1)\) について、 (2a) \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_1)\) かつ (2b) \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_2)\) が成り立つ。 |
このように言い換えて、\((Z/p_1p_2Z)^{*}\) での問題を、\((Z/p_1Z)^{*}\) と \((Z/p_2Z)^{*}\) の問題に置き換えます。Miller-Rabin の条件を満たす、
| \((Z/p_1p_2Z)^{*}\) | の部分集合を \(M\) | |
| \((Z/p_1Z)^{*}\) | の部分集合を \(M_1\) | |
| \((Z/p_2Z)^{*}\) | の部分集合を \(M_2\) |
とすると、元の数については、
\(|M|=|M_1|\cdot|M_2|\)
が成り立ちます。以降、（１）\(,\) （２） の条件ごとに \(|M_1|\) と \(|M_2|\) を見積もることで、条件ごとの \(|M|\) を見積もり、そこから目的である \(|M|\) の数を評価します。（１）\(,\) （２） の条件ごとの \(M\) については、既に上で使ったように、
（１）を満たす \(M\) の部分集合を \(A_1\)
（２）を満たす \(M\) の部分集合を \(A_2\)
とします。
\(n-1=2^ek\) とおいたのと同じように、
\(p_1-1=2^{e_1}k_1\) （\(e_1\geq1,\:k_1\)：奇数）
\(p_2-1=2^{e_2}k_2\) （\(e_2\geq1,\:k_2\)：奇数）
とします。ここで、
\(e_1\leq e_2\)
とします。\(p_1\) と \(p_2\) は入れ替えてもよいので、こうすることで一般性は失われません。まず初めに、\(e,\:e_1,\:e_2\) の関係を整理しておきます。\(n-1=2^ek\) の式ですが、
\(\begin{eqnarray}
&&\:\:n-1&=p_1\cdot p_2-1\\
&&&=(2^{e_1}k_1+1)\cdot(2^{e_2}k_2+1)-1\\
&&&=2^{e_1+e_2}k_1k_2+2^{e_1}k_1+2^{e_2}k_2\\
&&&=2^{e_1}(2^{e_2}k_1k_2+k_1+2^{e_2-e_1}k_2)\\
\end{eqnarray}\)
と計算されます。この式を、
\(n-1=2^{e_1}\cdot K\)
\(K=2^{e_2}k_1k_2+k_1+2^{e_2-e_1}k_2\)
と表わすと、
\(e_1 < e_2\) のときは、\(K\) は奇数なので \(e=e_1\)
\(e_1=e_2\) のときは、\(K\) は偶数なので \(e > e_1\)
となり、いずれにせよ、
\(e_1\leq e\)
です。
ちなみに、\(n=p_1p_2\cd p_m\:\:(m\geq3)\) のときも同様で、
\(p_i-1=2^{e_i}k_i\:(3\leq i\leq m)\)
としたとき、\(e_1\) を \(e_i\:(3\leq i\leq m)\) の最小値とすると、\(e_1\leq e\) です。
\(p_i-1=2^{e_i}k_i\:(3\leq i\leq m)\)
としたとき、\(e_1\) を \(e_i\:(3\leq i\leq m)\) の最小値とすると、\(e_1\leq e\) です。
以降、
\(e_1 < e_2\)
\(e_1=e_2\)
の２つに分けて証明します。
２．１ \(e_1 < e_2\) の場合
（１）が成立するとき
（１） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_1\) とします。巡回群に関する定理 \((\br{C})\) により、\((Z/pZ)^{*}\) の群位数は \(p-1\) なので、
\(a^k=1\) となる \((Z/p_1Z)^{*}\) の元は \(\mr{gcd}(k,\:p_1-1)\) 個
\(a^k=1\) となる \((Z/p_2Z)^{*}\) の元は \(\mr{gcd}(k,\:p_2-1)\) 個
です。また、\(n=p_1p_2\) のとき、
\((Z/nZ)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\)
の同型が成り立つので、
\(\begin{eqnarray}
&&\:\:|A_1|&=\mr{gcd}(k,\:p_1-1)\cdot\mr{gcd}(k,\:p_2-1)\\
&&&=\mr{gcd}(k,\:2^{e_1}k_1)\cdot\mr{gcd}(k,\:2^{e_2}k_2)\\
\end{eqnarray}\)
です。ここで、\(k,\:k_1,\:k_2\) は全て奇数です。従って、
\(\mr{gcd}(k,\:2^{e_1}k_1)=\mr{gcd}(k,\:k_1)\)
\(\mr{gcd}(k,\:2^{e_2}k_2)=\mr{gcd}(k,\:k_2)\)
が成り立ち、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
となります。ここで \(|A_1|\) の上限値を評価すると、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
であり、
\(|A_1|\leq k_1k_2\)
が結論づけられます。
（２）が成立するとき
（２） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_2\) とします。まず、\(0\leq r\leq e-1\) である \(r\) を一つ固定して考え、
\(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_1)\) かつ
\(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_2)\)
であるような集合を \(A_2(r)\) とします。そうすると、
\(|A_2|=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\)
が成り立ちます。まず、次を証明します。
\((Z/p_1Z)^{*}\) において \(a^{2^rk}=-1\) である \(a\) の個数は \(r\geq e_1\) のとき \(0\) 個 \(r < e_1\) のとき \(2^r\cdot\mr{gcd}(k,\:k_1)\) 個 である。 |
【証明】
\((Z/p_1Z)^{*}\) は群位数 \(p_1-1\) の巡回群なので、その生成元を \(g\) とする。ここで、
\(g^{\frac{p_1-1}{2}}\)
を考えると、生成元の定義上、\(g^{p_1-1}=1,\) \(g^x\neq1\:(1\leq x < p_1-1)\) なので、
\(\begin{eqnarray}
&&\:\:g^{\frac{p_1-1}{2}}&\neq1\\
&&\:\:(g^{\frac{p_1-1}{2}})^2&=1\\
\end{eqnarray}\)
であり、つまり、
\(g^{\frac{p_1-1}{2}}=-1\:(=p_1-1)\)
である。\(a^{2^rk}=-1\) が成り立つ \(a\) を、生成元 \(g\) を用いて、
\(a=g^x\:\:(1\leq x\leq p_1-1)\)
と表すと、
\(a^{2^rk}=-1\)
\((g^x)^{2^rk}=g^{\frac{p_1-1}{2}}\) \((\br{D})\)
だが、\(p_1-1=2^{e_1}k_1\) なので、
\(g^{2^rkx}=g^{2^{e_1-1}k_1}\)
が成り立つ。ここで一般的に \((Z/pZ)^{*}\) の生成元を \(g\) とし、
\(g^s=g^t\)
なら、\(j\) を整数として、
\(\begin{eqnarray}
&&\:\:g^{p-1}&=1\\
&&\:\:g^{j(p-1)}&=1\\
\end{eqnarray}\)
なので、
\(g^s=g^{t+j(p-1)}\)
である。つまり、
\(s\equiv t\:\:(\mr{mod}\:p-1)\)
が成り立つ。従って、
\(2^rkx\equiv2^{e_1-1}k_1\:\:(\mr{mod}\:p_1-1)\)
\(2^rkx\equiv2^{e_1-1}k_1\:\:(\mr{mod}\:2^{e_1}k_1)\)
\((\br{E})\)
であり、\((\br{E})\) 式は \((\br{D})\) 式と等価である。\((\br{E})\) 式を解いて \(x\) を求めると、そこから \(a=g^x\) で \(a\) が求まる。
ここで、\(r\geq e_1\) と仮定すると、\((\br{E})\) 式は、
\(2^rkx-2^{e_1-1}k_1\equiv0\:\:(\mr{mod}\:2^{e_1}k_1)\)
\(2^{e_1-1}(2^{r-e_1+1}kx-k_1)\equiv0\:\:(\mr{mod}\:2^{e_1}k_1)\)
\((\br{F})\)
と書ける。この \((\br{F})\) 式の \((2^{r-e_1+1}kx-k_1)\) の項に着目すると、\(r-e_1+1\geq1\) であり、\(k_1\) は奇数なので「偶数 － 奇数」＝「奇数」である。そうすると、\((\br{F})\) 式の左辺は \(2^{e_1-1}\) の奇数倍であり、法である \(2^{e_1}k_1\) では割り切れず、\((\br{F})\) 式は成り立たない。つまり、\(a^{2^rk}=-1\) の解は、\(r\geq e_1\) のときには無い。
一方、\(r < e_1\) のとき \((\br{E})\) 式は、
\(2^r(kx-2^{e_1-r-1}k_1)\equiv0\:\:(\mr{mod}\:2^{e_1}k_1)\)
\((\br{F}\,')\)
と書ける。この \((\br{F}\,')\) 式が成り立つためには、\((kx-2^{e_1-r-1}k_1)\) の項は約数として \(2^i\:(i\geq e_1-r\geq1)\) を持つ必要があるが（少なくとも偶数である必要）、\(kx\) と \(2^{e_1-r-1}k_1\) はともに奇数にも偶数にもなり得るので、 \((\br{F}\,')\) 式の成立可能性に問題はない。そこで、以降で \(r < e_1\) のときの \((\br{E})\) 式の解の個数を検討する。
\(2^rkx\equiv2^{e_1-1}k_1\:\:(\mr{mod}\:2^{e_1}k_1)\)
\((\br{E})\)
において、
\(\begin{eqnarray}
&&\:\:h&=\mr{gcd}(k,\:k_1)\\
&&\:\:k\,'&=\dfrac{k}{h}\\
&&\:\:k_1{}^{\prime}&=\dfrac{k_1}{h}\\
\end{eqnarray}\)
とおく。\(k\,'\) と \(k_1{}^{\prime}\) は互いに素で、また、\(k,\:k_1\) が奇数なので、\(h,\:k\,',\:k_1{}^{\prime}\) は奇数である。\(r < e_1\) つまり \(r\leq e_1-1\) の条件があるので、\((\br{E})\) 式の両辺と法を \(2^rh\) で割ると、
\(k\,'x\equiv2^{e_1-1-r}k_1{}^{\prime}\:\:(\mr{mod}\:2^{e_1-r}k_1{}^{\prime})\)
\((\br{G})\)
となる。一般的に、
\(ax\equiv b\:\:(\mr{mod}\:m)\)
の合同方程式は、\(a\) が \(m\) と素なときには \(b\) の値にかかわらず解があって、その解は \(m\) を法として唯一である（下記）。
一次不定方程式、
\(ax+my=b\)
は、\(\mr{gcd}(a,\:m)=1\) のときに解をもつ（No.355「高校数学で理解するガロア理論（２）：不定方程式の解の存在：21C」参照）。この等式の両辺を \(\mr{mod}\:m\) でみると、
\(ax\equiv b\:\:(\mr{mod}\:m)\)
の合同方程式となる。この方程式に \(x_1,\:x_2\) の２つの解があるとすると、
\(ax_1\equiv b\:\:(\mr{mod}\:m)\)
\(ax_2\equiv b\:\:(\mr{mod}\:m)\)
\(a(x_1-x_2)\equiv0\:\:(\mr{mod}\:m)\)
となるが、\(\mr{gcd}(a,\:m)=1\) なので、
\(x_1\equiv x_2\:\:(\mr{mod}\:m)\)
となり、解は \(m\) を法として唯一である。
\(ax+my=b\)
は、\(\mr{gcd}(a,\:m)=1\) のときに解をもつ（No.355「高校数学で理解するガロア理論（２）：不定方程式の解の存在：21C」参照）。この等式の両辺を \(\mr{mod}\:m\) でみると、
\(ax\equiv b\:\:(\mr{mod}\:m)\)
の合同方程式となる。この方程式に \(x_1,\:x_2\) の２つの解があるとすると、
\(ax_1\equiv b\:\:(\mr{mod}\:m)\)
\(ax_2\equiv b\:\:(\mr{mod}\:m)\)
\(a(x_1-x_2)\equiv0\:\:(\mr{mod}\:m)\)
となるが、\(\mr{gcd}(a,\:m)=1\) なので、
\(x_1\equiv x_2\:\:(\mr{mod}\:m)\)
となり、解は \(m\) を法として唯一である。
\((\br{G})\) 式 をみると、\(k\,'\) と \(k_1{}^{\prime}\) は互いに素であり、かつ奇数なので、\((\br{G})\) 式における \(k\,'\) と、法である \(2^{e_1-r}k_1{}^{\prime}\) は互いに素である。ということは、
\((\br{G})\) 式は、法 \(2^{e_1-r}k_1{}^{\prime}\) で唯一の解をもつ
ことになる。\((\br{G})\) 式は \((\br{E})\) 式の両辺と法を \(2^rh\) で割ったものであった。つまり、\((\br{G})\) 式の法は、
\(2^{e_1-r}k_1{}^{\prime}=\dfrac{2^{e_1}k_1}{2^rh}\)
である。ということは、\((\br{G})\) 式の、法 \(2^{e_1-r}k_1{}^{\prime}\) での唯一の解は、法 \(2^{e_1}k_1\) である \((\br{E})\) 式の解、\(2^rh=2^r\cdot\mr{gcd}(k,\:k_1)\) 個に対応する。\((\br{E})\) 式は \((\br{D})\) 式と等価なので、これで、
\(0\leq r\leq e-1\) である \(r\) を一つ固定して考えたとき、\((Z/p_1Z)^{*}\) において \(a^{2^rk}=-1\) である \(a\) の個数は
\(r\geq e_1\) のとき \(0\) 個
\(r < e_1\) のとき \(2^r\cdot\mr{gcd}(k,\:k_1)\) 個
\(r\geq e_1\) のとき \(0\) 個
\(r < e_1\) のとき \(2^r\cdot\mr{gcd}(k,\:k_1)\) 個
が証明できた。【証明終】
ここまでで、
\((Z/p_1Z)^{*}\) において \(a^{2^rk}=-1\) である \(a\) の個数は
\(r\geq e_1\) のとき \(0\) 個
\(r < e_1\) のとき \(2^r\cdot\mr{gcd}(k,\:k_1)\) 個
であることが分かりました。この議論は \((Z/p_2Z)^{*}\) のときにも全く同じようにできて、
\((Z/p_2Z)^{*}\) において \(a^{2^rk}=-1\) である \(a\) の個数は
\(r\geq e_2\) のとき \(0\) 個
\(r < e_2\) のとき \(2^r\cdot\mr{gcd}(k,\:k_2)\) 個
が言えます。この結果を踏まえて、
| \(|A_2(r)|\)： | \((Z/p_1p_2Z)^{*}\) において | |
| \(a^{2^rk}=-1\) である \(a\) の個数 |
を求めます。これは、
\((Z/p_1p_2Z)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\)
の直積関係を利用すると、\(e_1 < e_2\) の関係を考慮して、
\(r < e_1\) のとき
\(\begin{eqnarray}
&&\:\: |A_2(r)|&=2^r\cdot\mr{gcd}(k,\:k_1)\cdot2^r\cdot\mr{gcd}(k,\:k_2)\\
&&&=4^r\cdot\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\\
\end{eqnarray}\)
\(r\geq e_1\) のとき
\(|A_2(r)|=0\)
となります。ここから \(|A_2|\) を計算するには、
\(|A_2|=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\)
ですが、\(e_1\leq e\) の関係があるので、\(e-1\) までの総和は \(e_1-1\) までの総和に等しいことになります。つまり、
\(\begin{eqnarray}
&&\:\:|A_2|&=\displaystyle\sum_{r=0}^{e-1}|A_2(r)|\\
&&&=\displaystyle\sum_{r=0}^{e_1-1}|A_2(r)|\\
&&&=\displaystyle\sum_{r=0}^{e_1-1}4^r\cdot\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\\
\end{eqnarray}\)
の式が成り立ちます。この式に等比数列の総和である、
\(\displaystyle\sum_{r=0}^{e_1-1}4^r=\dfrac{4^{e_1}-1}{4-1}=\dfrac{4^{e_1}-1}{3}\)
を代入すると、
\(|A_2|=\dfrac{4^{e_1}-1}{3}\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
です。ここで、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
の関係を利用すると、
\(|A_2|\leq\dfrac{4^{e_1}-1}{3}k_1k_2\)
となります。ここまでの式は、\(e_1 < e_2\) でなくても \(e_1\leq e_2\) なら成り立つことが導出過程から分かります。
以上の計算で \(|M|\) を評価できます。
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&\leq k_1k_2+\dfrac{4^{e_1}-1}{3}k_1k_2\\
\end{eqnarray}\)
この計算をもとに \(1\leq a\leq n-1\) の \(n-1\) 個のうちの \(|M|\) の割合を評価すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&=\dfrac{|M|}{p_1p_2-1}\\
&&& < \dfrac{|M|}{(p_1-1)(p_2-1)}\\
&&&=\dfrac{|M|}{2^{e_1}k_1\cdot2^{e_2}k_2}\\
&&&\leq\dfrac{1}{2^{e_1+e_2}}\left(1+\dfrac{4^{e_1}-1}{3}\right)\\
&&&=\dfrac{1}{2^{e_1+e_2}}\cdot\dfrac{2+4^{e_1}}{3}\\
\end{eqnarray}\)
となります。ここで、\(\bs{e_1 < e_2}\) なので、\(\bs{2e_1+1\leq e_1+e_2}\) です。従って、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{2^{2e_1+1}}\cdot\dfrac{2+4^{e_1}}{3}\\
&&&=\dfrac{2+4^{e_1}}{6\cdot4^{e_1}}\\
\end{eqnarray}\)
ですが、この最後の式の最大値は \(e_1=1\) のときです。これを代入すると、
\(\dfrac{|M|}{n-1} < \dfrac{6}{24}=\dfrac{1}{4}\)
となって、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は \(e_1 < e_2\) のときに \(\dfrac{1}{4}\) 未満であることが証明されました。
２．２ \(e_1=e_2\) の場合
（１）が成立するとき
\(e_1 < e_2\) と全く同じ考え方で、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
です（\(k,\:k_1,\:k_2\) は奇数）。ここで、一般的には、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
が成り立ちますが、\(e_1=e_2\) だと、
\(\mr{gcd}(k,\:k_1)=k_1\)
\(\mr{gcd}(k,\:k_2)=k_2\)
が同時に成り立つことはありません。なぜなら、同時に成り立つとすると、
\(k_1\mid k\) かつ \(k_2\mid k\)
ですが、\(n-1=2^ek\) だったので、
\(k_1\mid(n-1)\) かつ \(k_2\mid(n-1)\)
です。ここで、\(n-1\) は
\(\begin{eqnarray}
&&\:\:n-1&=p_1p_2-1\\
&&&=(1+2^{e_1}k_1)\cdot p_2-1\\
&&&\equiv p_2-1\:\:(\mr{mod}\:k_1)\\
\end{eqnarray}\)
となりますが、\(k_1\mid(n-1)\) なので、
\(k_1\mid(p_2-1)\)
\(k_1\mid2^{e_2}k_2\)
\(k_1\mid k_2\)
となります。まったく同様にして、
\(n-1\equiv p_1-1\:\:(\mr{mod}\:k_2)\)
\(k_2\mid(p_1-1)\)
\(k_2\mid2^{e_1}k_1\)
\(k_2\mid k_1\)
です。\(k_1\mid k_2\) かつ \(k_2\mid k_1\) ということは、\(k_1=k_2\) ですが、\(e_1=e_2\) なので、\(p_1=p_2\) となって矛盾します。つまり \(\mr{gcd}(k,\:k_1)=k_1\)、\(\mr{gcd}(k,\:k_2)=k_2\) が同時に成り立つことはありません。そこで、
\(\mr{gcd}(k,\:k_1) < k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
として一般性を失いません。ここで \(k_1\) を素因数分解したときに現れる最小の素数を \(q\:(q\geq3)\)とし、
\(k_1=q\cdot k_0\:\:(k_0\)：奇数\()\)
と表します。そうすると、\(\mr{gcd}(k,\:k_1) < k_1\) なので、
\(\mr{gcd}(k,\:k_1)\leq k_0\)
が成り立ち、
\(\dfrac{k_1}{\mr{gcd}(k,\:k_1)}\geq\dfrac{k_1}{k_0}=q\geq3\)
となります。ここから、
\(\mr{gcd}(k,\:k_1)\leq\dfrac{1}{3}k_1\)
が得られます。そこで、
\(\mr{gcd}(k,\:k_1)\leq\dfrac{1}{3}k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
をもとに、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
を評価すると、
\(|A_1|\leq\dfrac{1}{3}k_1k_2\)
となります。
（２）が成立するとき
このケースは \(e_1 < e_2\) で導出した、
\(|A_2|\leq\dfrac{4^{e_1}-1}{3}\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\)
までは全く同じです。ここで、
\(\mr{gcd}(k,\:k_1)\leq\dfrac{1}{3}k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
によって評価すると、
\(|A_2|\leq\dfrac{1}{3}\cdot\dfrac{4^{e_1}-1}{3}k_1k_2\)
が成り立ちます。
以上の計算から \(|M|\) を評価すると、
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&\leq\dfrac{1}{3}k_1k_2+\dfrac{1}{3}\cdot\dfrac{4^{e_1}-1}{3}k_1k_2\\
\end{eqnarray}\)
この計算をもとに \(1\leq a\leq n-1\) の \(n\) 個のうちの \(|M|\) の割合を計算すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&=\dfrac{|M|}{p_1p_2-1}\\
&&& < \dfrac{|M|}{(p_1-1)(p_2-1)}\\
&&&=\dfrac{|M|}{2^{e_1}k_1\cdot2^{e_2}k_2}\\
&&&\leq\dfrac{1}{2^{e_1+e_2}}\cdot\dfrac{1}{3}\left(1+\dfrac{4^{e_1}-1}{3}\right)\\
&&&=\dfrac{1}{2^{2e_1}}\cdot\dfrac{1}{3}\cdot\dfrac{2+4^{e_1}}{3}\\
&&&=\dfrac{1}{4^{e_1}}\cdot\dfrac{1}{3}\cdot\dfrac{2+4^{e_1}}{3}\\
&&&=\dfrac{1}{3}\left(\dfrac{2}{3\cdot4^{e_1}}+\dfrac{1}{3}\right)\\
\end{eqnarray}\)
となります。この最後の式の最大値は \(e_1=1\) のときです。代入すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{3}\left(\dfrac{1}{6}+\dfrac{1}{3}\right)\\
&&&=\dfrac{1}{6} < \dfrac{1}{4}\\
\end{eqnarray}\)
となって、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は、\(e_1=e_2\) のときにも \(\dfrac{1}{4}\) 未満であることが証明されました。
３． \(n=p_1\cdot p_2\cdot\cd\cdot p_m\:\:(\:m\geq3\:)\)
\(n\) が３個以上の相異なる奇素数の積に素因数分解される場合です。この場合も、基本的には \(n=p_1\cdot p_2\) のケースと（全く同じではないが）同様になります。Miller-Rabin の定理を再掲します。
Miller-Rabin の定理（再掲） \(n\) を \(3\) 以上の奇数の合成数とする。また、\(n-1=2^ek\:\:(e\geq1,\:k\) は奇数\()\) と表されているものとする。このとき、 Miller-Rabin の条件 （１） \(a^k\equiv1\:\:(\mr{mod}\:n)\) もしくは （２） ある \(r\:(0\leq r\leq e-1)\) について、 \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:n)\) を満たす \(a\:(1\leq a\leq n-1)\) は、\(n-1\) 個のうちの \(1/4\) 以下である。 |
以降、表記を見やすくするため、\(m=3\)、\(n=p_1\cdot p_2\cdot p_3\) の場合で記述します。既約剰余類群の同型関係、
\((Z/p_1p_2p_3Z)^{*}\cong(Z/p_1Z)^{*}\times(Z/p_2Z)^{*}\times(Z/p_3Z)^{*}\)
を利用して、問題を置き換えます。それぞれの群位数は、
\(\begin{eqnarray}
&&\:\:|(Z/p_1p_2p_3Z)^{*}|&=\varphi(p_1p_2p_3)\\
&&&=(p_1-1)(p_2-1)(p_3-1)\\
\end{eqnarray}\)
\(|(Z/p_1Z)^{*}|=\varphi(p_1)=p_1-1\)
\(|(Z/p_2Z)^{*}|=\varphi(p_2)=p_2-1\)
\(|(Z/p_3Z)^{*}|=\varphi(p_3)=p_3-1\)
であり、
\(|(Z/p_1p_2p_3Z)^{*}|=|(Z/p_1Z)^{*}|\cdot|(Z/p_2Z)^{*}|\cdot|(Z/p_3Z)^{*}|\)
が成り立ちます。Miller-Rabin の条件は次のように言い換えられます。
\(n=p_1p_2p_3,\:\:n-1=2^ek\) とするとき、 （１） (1a) \(a^k\equiv1\:\:(\mr{mod}\:p_1)\) かつ (1b) \(a^k\equiv1\:\:(\mr{mod}\:p_2)\) かつ (1c) \(a^k\equiv1\:\:(\mr{mod}\:p_3)\) もしくは、 （２） ある \(r\:(0\leq r\leq e-1)\) について、 (2a) \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_1)\) かつ (2b) \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_2)\) かつ (2c) \(a^{2^rk}\equiv-1\:\:(\mr{mod}\:p_3)\) が成り立つ。 |
例によって、
\(p_1-1=2^{e_1}k_1\:\:(e_1\geq1,\:k_1\) は奇数\()\)
\(p_2-1=2^{e_2}k_2\:\:(e_2\geq1,\:k_2\) は奇数\()\)
\(p_3-1=2^{e_3}k_3\:\:(e_3\geq1,\:k_3\) は奇数\()\)
とおきますが、\(\bs{e_1}\) は \(\bs{e_1,\:e_2,\:e_3}\) のうちの最小とします。こう仮定して一般性を失うことはありません。この仮定のもとでは、
\(3e_1\leq e_1+e_2+e_3\)
が成り立ちます。等号は \(e_1=e_2=e_3\) の場合です。
（１）が成立するとき
（１） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_1\) とします。\(n=p_1\cdot p_2\) のケースと同様の計算によって、
\(|A_1|=\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\cdot\mr{gcd}(k,\:k_3)\)
となります。\(|A_1|\) の上限値を評価すると、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
\(\mr{gcd}(k,\:k_3)\leq k_3\)
なので、
\(|A_1|\leq k_1k_2k_3\)
が結論づけられます。
（２）が成立するとき
（２） を満たす \(a\:(1\leq a\leq n-1)\) の集合を \(A_2\) とします。\(n=p_1\cdot p_2\) のケースと同様の計算で、
\(|A_2|=\displaystyle\sum_{r=0}^{e_1-1}(2^r)^3\cdot\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\cdot\mr{gcd}(k,\:k_3)\)
です。この式に \(e_1\) だけが現れるのは、\(e_1\) が \(\{e_1,\:e_2,\:e_3\}\) の最小値だからです。ここで、
\(\mr{gcd}(k,\:k_1)\leq k_1\)
\(\mr{gcd}(k,\:k_2)\leq k_2\)
\(\mr{gcd}(k,\:k_3)\leq k_3\)
の関係を利用します。また、等比数列の総和を計算すると、
\(\begin{eqnarray}
&&\:\:\displaystyle\sum_{r=0}^{e_1-1}(2^r)^3&=\displaystyle\sum_{r=0}^{e_1-1}(2^3)^r\\
&&&=\dfrac{(2^3)^{e_1}-1}{2^3-1}\\
\end{eqnarray}\)
です。まとめると、
\(|A_2|\leq\dfrac{2^{3e_1}-1}{2^3-1}\cdot k_1k_2k_3\)
が得られます。
以上をもとに \(|M|\) を評価すると、
\(\begin{eqnarray}
&&\:\:|M|&=|A_1|+|A_2|\\
&&&\leq k_1k_2k_3+\dfrac{2^{3e_1}-1}{2^3-1}\cdot k_1k_2k_3\\
\end{eqnarray}\)
です。この計算をもとに \(1\leq a\leq n-1\) の \(n-1\) 個のうちの \(|M|\) の割合を計算すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}&=\dfrac{|M|}{p_1p_2p_3-1}\\
&&& < \dfrac{|M|}{(p_1-1)(p_2-1)(p_3-1)}\\
&&&=\dfrac{|M|}{2^{e_1}k_1\cdot2^{e_2}k_2\cdot2^{e_3}k_3}\\
&&&\leq\dfrac{1}{2^{e_1+e_2+e_3}}\left(1+\dfrac{2^{3e_1}-1}{2^3-1}\right)\\
\end{eqnarray}\)
となります。ここで、\(3e_1\leq e_1+e_2+e_3\) です。従って、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{2^{3e_1}}\left(1+\dfrac{2^{3e_1}-1}{2^3-1}\right)\\
&&&=\dfrac{6+2^{3e_1}}{7\cdot2^{3e_1}}\\
\end{eqnarray}\)
ですが、この最後の式は \(e_1\) の増大によって単調減少するので、その最大値は \(e_1=1\) のときです。これを代入すると、
\(\dfrac{|M|}{n-1} < \dfrac{6+8}{56}=\dfrac{1}{4}\)
となって、\(1\leq a\leq n-1\) のなかで Miller-Rabin の条件を満たす数の比率は \(\dfrac{1}{4}\) 未満であることが確かめられました。
以上の表記は \(m=3\) の場合ですが、証明のプロセスを振り返ってみると、\(m\geq3\) のときは、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{1}{2^{m\cdot e_1}}\left(1+\displaystyle\sum_{r=0}^{e_1-1}(2^m)^r\right)\\
&&&=\dfrac{1}{2^{m\cdot e_1}}\left(1+\dfrac{2^{m\cdot e_1}-1}{2^m-1}\right)\\
&&&=\dfrac{2^m-2+2^{m\cdot e_1}}{(2^m-1)\cdot2^{m\cdot e_1}}\\
\end{eqnarray}\)
です。この式の右辺は \(e_1\) について単調減少なので、\(e_1=1\) を代入すると、
\(\begin{eqnarray}
&&\:\:\dfrac{|M|}{n-1}& < \dfrac{2^m-2+2^m}{(2^m-1)\cdot2^m}\\
&&&=\dfrac{2\cdot(2^m-1)}{(2^m-1)\cdot2^m}\\
&&&=\dfrac{1}{2^{m-1}}\\
&&&\leq\dfrac{1}{4}\\
\end{eqnarray}\)
が \(m\geq3\) のすべてで成り立ちます。
ちなみに、カーマイケル数は必ず、\(p_1\cdot p_2\cdot\cd\cdot p_m\) \((\:m\geq3\:)\) の形をしていることが知られています。上の証明によって、\(n\) がカーマイケル数であったとしても Miller-Rabin の条件を満たす底 \(a\) は 全体の \(\dfrac{1}{4}\) 未満であることが分かります。
以上で、Miller-Rabin の定理が証明されました。
| 1024 ビットの素数を求める |
Miller-Rabin の定理を使って、実際に巨大素数を求めてみます。2048 ビットの RSA 暗号で使われる 1024 ビットの素数を求めます。1024 ビットは、\(2^{1023}\) ～ \(2^{1024}-1\) の数です。Python で整数 n が素数かどうかを判定する関数、miller_rabin(n) を次のようにシンプルに実装します。n が素数なら True、合成数なら False を返す関数です。反復回数は40回とします。
from random import randint
def miller_rabin(n):
if n == 2:
return True
if n < 2 or n % 2 == 0:
return False
k = (n - 1) // 2
e = 1;
while k % 2 == 0:
e += 1
k = k // 2
iteration = 40
for _ in range(iteration):
if not mr_base(n, e, k):
return False
return True
def mr_base(n, e, k):
a = randint(1, n - 1)
b = pow(a, k, n)
if (b == 1) or (b == n - 1):
return True
else:
for _ in range(e - 1):
b = pow(b, 2, n)
if b == n - 1:
return True
return False
|
この関数を用いて作ったのは、次のようなプログラムです。
| \(2^{1023}\) ～ \(2^{1024}-1\) の間の乱数 \(n\) を \(10,000\)個、順々に発生させる。 | |
| miller_rabin(n) で \(n\) が素数かどうかを調べる。 | |
| 見つかった素数の個数をカウントする。 | |
| 最初に見つかった素数を出力する。 |
１つの実行例ですが、12個の素数が見つかり、最初に見つかったのは次に示す 308桁の素数でした。実行時間は Google Colaboratry の環境で約 30秒です。
94872061 3054580553 8024546417 0443276752 8208705264 5738921481
0677834138 4405922941 9044925712 7675055467 0399951005
3184840724 4107587320 1847375774 1842027537 2972168431
3292460096 0558147125 1513790454 1422818823 6684614711
0137905023 0947309459 7845156412 5542386383 6759057622
9952488549 9964568003 6095666702 5172908475 7410497807
何回か実行してみると、素数の桁数はほとんどが 309桁で、一部が 308桁です。これは \(\mr{log}_{10}2^{1023}\fallingdotseq307.95\) なので、そうなるはずです。また、１万個の n のうちの素数の数は 8～18 個程度となりました。実行結果について「素数定理」と「反復回数」の観点から考察します。
素数定理
数学では、\(x\) 以下の素数の個数を \(\pi(x)\) で表わします。素数定理によると、
\(\pi(x)\sim\dfrac{x}{\mr{log}(x)}\)
です。左辺と右辺をつなぐ \(\sim\) は、
左辺と右辺の比率 \(\longrightarrow\:1\:\:(x\longrightarrow\infty)\)
を意味します。以下、
\(\pi(x)=\dfrac{x}{\mr{log}(x)}\)
と考えて、m ビットの数に含まれる素数の割合を見積もります。m ビットの数の総数は \(2^{m-1}\) 個なので、m ビット数の素数割合は、
| 素数割合 | \(=\dfrac{1}{2^{m-1}}(\pi(2^m)-\pi(2^{m-1}))\) | |
| \(=\dfrac{1}{\mr{log}2\cdot m}\cdot\dfrac{m-2}{m-1}\) |
ですが、\(\dfrac{m-2}{m-1}\) を \(1\) と見なすと、簡潔に、
素数割合 \(=\dfrac{1}{\mr{log}2\cdot m}\)
です。この式に \(m=1024\) を代入すると、
素数割合 \(\fallingdotseq0.0014\)
となります。つまり、
1024 ビットの数、10,000個をランダムに選んで素数判定を行うと、0.14%=14 個程度の素数が見つかる
と言えます。これは上の実験で、１万個の n のうちの素数の数は 8～18 個程度だったことに合致します。
反復回数
プログラムを少々変更して、
何回目の反復（iteration）で素数\(\cdot\)合成数の判定ができたか
を調べると、素数判定のときは当然 iteration = 40 ですが、
合成数判定のときの iteration = 1
であることが分かります（１万個の素数判定をする前提です）。つまり、\(n\) が合成数なら最初の計算で即、合成数と判明します。何回かの反復の後に合成数と判明することは、上の計算では無いのです。
この理由は、\(n\) が合成数だと「\(a\:(1\leq a\leq n-1)\) のなかで Miller-Rabin の条件を満たす底 \(a\) の比率は \(\tfrac{1}{4}\) 以下」という定理の \(\tfrac{1}{4}\) が（一般には）過大評価であることによります。たとえば、\(n\) が２つの異なる素数の積の場合、
\(\begin{eqnarray}
&&\:\:n&=p_1p_2\\
&&\:\:n-1&=2^ek\\
&&\:\:p_1-1&=2^{e_1}k_1\\
&&\:\:p_2-1&=2^{e_2}k_2\\
\end{eqnarray}\)
（\(e,e_1,e_2\geq1,\:\:k,k_1,k_2\) は奇数）
において \(\tfrac{1}{4}\) 以下の主な根拠は、
\(\mr{gcd}(k,\:k_1)\cdot\mr{gcd}(k,\:k_2)\leq k_1k_2\)
でした。ところが、この式で等号が成り立つのは、特に \(n\) が巨大だと、めったにありません。高々 10,000個程度の合成数を判定したとしても、Miller-Rabin の条件を満たす底 \(a\) が現れる確率はほとんどゼロに等しいのです。
ランダムに選んだ数 \(n\) のほとんどは（1024 ビットの数の場合 99.86 % は）合成数です。したがって「合成数を合成数だと速く判定する」のが素数判定アルゴリズムのポイントであり、反復回数をどうするかは全体の速度にそれほど関係ありません。このあたりの事情はフェルマの条件で素数判定をしても同じです。
ただし、フェルマの条件とは違って、ランダムに選んだ底 \(a\) が Miller-Rabin の条件を満たす確率が、\(n\) の値にかかわらず必ず \(\tfrac{1}{4}\) 以下であることが数学的に保証されています。そこが Miller-Rabin の素数判定アルゴリズムの価値なのでした。
2024-03-18 18:23
nice!(0)
