Miller-Rabin素数判定法

$p^e\mid x^2-1=(x-1)(x+1)$ である。$p$ が $x-1$ と $x+1$ の両方を割るなら、差の $2$ も割るが、$p$ は奇数なので起こらない。よって $p$ はどちらか一方とは互いに素であり、$p^e$ はもう一方を割る。$\square$

$1\le a\le n-1$ とすると、$n$ は素数なので $n\nmid a$ であり、Fermatの小定理 により $a^{2^st}=a^{n-1}\equiv1\pmod n$ である。$a^t\equiv1$ なら条件 1 を満たす。そうでなければ、$a^{2^jt}\equiv1$ となる $j\in\{0,1,\dots,s\}$ のうち最小のものを $j_0$ とすると $j_0\ge1$ である。$x:=a^{2^{j_0-1}t}$ とおくと $x^2=a^{2^{j_0}t}\equiv1$ なので、lem-mr-square-roots（$e=1$）により $x\equiv\pm1$ である。$j_0$ の最小性から $x\not\equiv1$ なので $x\equiv-1$ であり、$j:=j_0-1\le s-1$ について条件 2 が成り立つ。
後半：$n$ が素数ならどの回で選んだ $a$ も $L(n)$ に入るので、どの回も通過し、出力は「おそらく素数」である。対偶をとると、「合成数」と出力されたなら $n$ は合成数である。$\square$

$G:=(\mathbb Z/n\mathbb Z)^\times$、$G_i:=(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ とおき、$\varphi_i:=\lvert G_i\rvert=p_i^{e_i-1}(p_i-1)$ と書く。def-mr-condition のあとに述べたとおり $L(n)\subset G$ とみなせる。中国剰余定理 により、$a\bmod n\mapsto(a\bmod p_1^{e_1},\dots,a\bmod p_r^{e_r})$ は群の同型 $G\cong G_1\times\cdots\times G_r$ を与える。$p_i$ は奇素数なので、各 $G_i$ は位数 $\varphi_i$ の 巡回群 である（原始根 の記事の定理「原始根が存在する法」）。$a\in G$ の $G_i$ への成分を $a_i$ と書く。
段 1（$r=1$ の場合）． $n=p^e$、$e\ge2$ とする。$a\in L(n)$ なら $a^{n-1}\equiv1\pmod n$ なので、$L(n)$ は 擬素数 の記事の定義「擬素数にする底の集合」の $B(n)$ に含まれる。同記事の定理「擬素数にする底の個数」により $\lvert B(n)\rvert=\gcd(p-1,n-1)$ であり、$n-1=p^e-1$ は $p-1$ の倍数なので、これは $p-1$ に等しい。また $n-1=(p-1)(1+p+\cdots+p^{e-1})$ で、$e\ge2$ から $1+p+\cdots+p^{e-1}\ge1+p$ なので、$p-1\le(n-1)/(p+1)\le(n-1)/4$ である（$p\ge3$）。
以下 $r\ge2$ とする。
段 2（指数 $m$ の選び方）． $t$ は奇数なので $(-1)^t=-1$ であり、$a=-1\in G$ について $a^{2^0t}\equiv-1$ が成り立つ。そこで、ある $a\in G$ について $a^{2^jt}\equiv-1\pmod n$ となる $j\in\{0,1,\dots,s-1\}$ のうち最大のものを $\nu$ とし、$m:=2^\nu t$ とおく。$a^m\equiv-1\pmod n$ を満たす $b\in G$ を 1 つ固定する。
段 3（$L(n)$ を含む部分群 $H$）． $H:=\{a\in G\mid a^m\equiv\pm1\pmod n\}$ とおく。$a\in L(n)$ とする。条件 1 の $a^t\equiv1$ なら $a^m=(a^t)^{2^\nu}\equiv1$ である。条件 2 の $a^{2^jt}\equiv-1$（$0\le j\le s-1$）なら、$\nu$ の最大性から $j\le\nu$ であり、$j=\nu$ なら $a^m\equiv-1$、$j<\nu$ なら $a^m=(a^{2^jt})^{2^{\nu-j}}\equiv1$ である。よって $L(n)\subset H$ である。$a^m,c^m\in\{\pm1\}$ なら $(ac)^m=a^mc^m\in\{\pm1\}$ なので、$H$ は積で閉じた有限群 $G$ の空でない部分集合であり、部分群である（各元の冪は有限個しかないので、逆元もその冪として $H$ に入る）。
段 4（各成分での個数）． $g_i:=\gcd(m,\varphi_i)$ とおく。$G_i$ で $b_i^m=-1$ かつ $b_i^{2m}=1$ であり、$p_i$ は奇数なので $G_i$ で $-1\ne1$ である。したがって $b_i$ の位数は $2m$ を割るが $m$ を割らない。$m=2^\nu t$（$t$ は奇数）なので、位数を割る $2$ の冪はちょうど $2^{\nu+1}$ であり、位数は $\varphi_i$ を割るから、$2^{\nu+1}\mid\varphi_i$ である。
擬素数 の記事の補題「巡回群で $x^k=1$ を満たす元の個数」により、$x^m=1$ を満たす $x\in G_i$ はちょうど $g_i$ 個ある。$x^m=-1$ を満たす $x\in G_i$ 全体は、$b_i$ と「$x^m=1$ を満たす元の全体」の積の集合（$x\mapsto b_ix$ による像）に等しいので、これもちょうど $g_i$ 個ある。さらに $x^m=\pm1$ と $x^{2m}=1$ は同値である（$x^{2m}=1$ なら $y=x^m$ は $y^2=1$ を満たし、lem-mr-square-roots により $y=\pm1$）。$2m$ と $\varphi_i$ はどちらも $2^{\nu+1}$ で割り切れ、$2m$ は $2^{\nu+2}$ で割り切れないので、$\gcd(2m,\varphi_i)=2\gcd(m,\varphi_i)=2g_i$ である。よって $x^m=\pm1$ を満たす $x\in G_i$ はちょうど $2g_i$ 個ある。
段 5（$H$ を含む部分群 $J$）． $J:=\{a\in G\mid\text{すべての }i\text{ について }a_i^m=\pm1\}$ とおく。段 3 と同じ理由で $J$ は $G$ の部分群であり、$H\subset J$ である。中国剰余定理による同型と段 4 から、
$$ \lvert J\rvert=\prod_{i=1}^r2g_i=2^r\prod_{i=1}^rg_i $$
である。一方、$a^m\equiv1\pmod n$ はすべての $i$ で $a_i^m=1$ となることと、$a^m\equiv-1\pmod n$ はすべての $i$ で $a_i^m=-1$ となることと同値なので、
$$ \lvert H\rvert=\prod_{i=1}^rg_i+\prod_{i=1}^rg_i=2\prod_{i=1}^rg_i=\frac{\lvert J\rvert}{2^{r-1}} $$
である。以上から
$$ \lvert L(n)\rvert\le\lvert H\rvert=\frac{\lvert J\rvert}{2^{r-1}}\le\frac{\varphi(n)}{2^{r-1}} $$
を得る。$r\ge3$ ならこれで 2 の主張が示され、$2^{r-1}\ge4$ なので $\lvert L(n)\rvert\le\varphi(n)/4$ でもある。
段 6（$r=2$ の場合）． $J\ne G$ を示す。$J=G$ と仮定すると、すべての $x\in G_i$ が $x^{2m}=1$ を満たす。$G_i$ は位数 $\varphi_i$ の巡回群なので、生成元を考えて $\varphi_i\mid2m$ である。$\nu\le s-1$ なので $2m=2^{\nu+1}t$ は $2^st=n-1$ を割り、$p_i^{e_i-1}(p_i-1)=\varphi_i\mid n-1$ となる。$p_i\mid n$ なので $p_i\nmid n-1$ であり、$e_i=1$ でなければならない。よって $n=p_1p_2$ で、$p_1-1\mid n-1$、$p_2-1\mid n-1$ である。ところが
$$ n-1=p_1p_2-1=(p_1-1)p_2+(p_2-1) $$
なので $p_1-1\mid p_2-1$ であり、$p_1,p_2$ を入れ替えた式から $p_2-1\mid p_1-1$ でもある。したがって $p_1=p_2$ となり、相異なることに反する。よって $J$ は $G$ の真の部分群であり、Lagrangeの定理 により $\lvert J\rvert\le\varphi(n)/2$ である。段 5 の不等式（$r=2$）から $\lvert L(n)\rvert\le\lvert J\rvert/2\le\varphi(n)/4$ である。
段 7（まとめ）． $r\ge2$ のとき、$1\le p_1\le n-1$ は $n$ と互いに素でないので $\varphi(n)\le n-2< n-1$ であり、$\lvert L(n)\rvert\le\varphi(n)/4<(n-1)/4$ である。$r=1$ の場合は段 1 で示した。$\square$

1 は thm-mr-prime である。2：各回の $a$ は $\{1,\dots,n-1\}$ から一様に選ばれるので、その回が通過する確率は $\lvert L(n)\rvert/(n-1)$ であり、thm-mr-quarter により $1/4$ 以下である。「おそらく素数」と出力されるのは $k$ 回とも通過したときに限り、各回の選び方は独立なので、その確率は $\bigl(\lvert L(n)\rvert/(n-1)\bigr)^k\le4^{-k}$ である。$\square$

$n-1=2^st$ なので、$n-1$ の 2 進法の桁数は $\operatorname{len}(t)+s$ であり、$\ell$ 以下である（$s$ と $t$ は $n-1$ の 2 進表示の末尾の $0$ を数えれば求まる）。計算整数論 の記事の定理「反復二乗法の正しさと手間」により、$a^t\bmod n$ は法 $n$ での掛け算 $2\operatorname{len}(t)$ 回以下で求まる。そのあと 2 乗を高々 $s-1$ 回行うので、掛け算は合わせて $2\operatorname{len}(t)+s-1<2\ell$ 回以下である。各回の掛け算と $n$ で割った余りの計算は、$n$ 未満の数どうしなので時間 $O(\ell^2)$ である（同記事の注意「基本演算の手間（この記事では証明しない）」）。よって 1 回の判定は $O(\ell^3)$ であり、それを $k$ 回くり返すので全体は $O(k\ell^3)$ である。$\square$

$M$ が合成数であることと $M>n$ は、擬素数 の記事の定理「擬素数 $n$ から $2^n-1$ を作る」の証明の前半による（$n=rs'$、$1< r< n$ と分けると $2^r-1$ が $M$ の自明でない約数になる）。$M$ は奇数で、$M-1=2^n-2=2(2^{n-1}-1)$ であり、$n\ge2$ なので $2^{n-1}-1$ は奇数である。よって $M$ について $s=1$、$t=2^{n-1}-1$ である。仮定から $n\mid2^{n-1}-1=t$ なので $t=nq$ と書ける。$2^n=M+1\equiv1\pmod M$ なので、
$$ 2^t=(2^n)^q\equiv1\pmod M $$
であり、def-mr-condition の条件 1 により $M$ は底 $2$ の強擬素数である。
$341=11\cdot31$ は底 $2$ の擬素数なので、$n_0:=341$、$n_{i+1}:=2^{n_i}-1$ と定めると、$n_{i+1}$ は底 $2$ の強擬素数であり、とくに底 $2$ の擬素数でもある（擬素数 の記事の命題「強い条件は Fermat の条件を含む」）。よって帰納的に、$n_1< n_2<\cdots$ はすべて底 $2$ の強擬素数である。$\square$