第1章暗号のための整数論と計算量

この章の目標

• 整数の大きさをビット長で測り、四則演算・ユークリッドの互除法・冪剰余がビット長の多項式時間で計算できることを証明できる
• 拡張ユークリッドの互除法で法 $n$ の逆元を求め、中国剰余定理で RSA の復号を高速化できる
• 素数定理から、ランダムに選んだ $k$ ビットの整数が素数である確率を見積もれる
• フェルマーテストの限界をカーマイケル数とコルセルトの判定法で説明し、ミラー–ラビン法の誤り確率が $1/4$ 以下であることを証明できる
• 鍵となる素数の生成で、乱数の質が安全性を左右する理由を説明できる

前提：04-algebra 第1章（合同式・中国剰余定理・オイラーの定理・原始根）、04-algebra 第2章（ラグランジュの定理・元の位数）。1.5 節では素数定理（05-complex-analysis 第8章で証明される）の主張だけを使う。

https で始まる Web ページを開くと、ブラウザとサーバーは数十ミリ秒のうちに数百桁の整数の冪剰余などを計算して、鍵を共有し、相手が本物であることを確かめる（TLS。第2章）。一方でその安全性は、「617 桁の整数の素因数分解には、現在知られている方法では天文学的な時間がかかる」といった事実に支えられている。公開鍵暗号は、速く計算できることと、速く計算する方法が知られていないことの落差の上に作られている。

本章ではこの落差の「易しい側」を確かめる。計算の速さの物差しを定め、逆元や冪剰余が多項式時間で計算できることを証明したあと、RSA の鍵に必要な大きな素数の見つけ方を考える。ミラー–ラビン法を使えば、素因数を一つも見つけないまま合成数であることを見抜ける。素数かどうかの判定は易しく、素因数分解は難しい――この非対称性が RSA 暗号の土台である。「難しい側」のアルゴリズムは第3章で扱う。

1.1 計算量の考え方

現在推奨される RSA の法は 2048 ビット（10 進で 617 桁）以上である（第2章）。このような数の計算の手間は、数の大きさではなく桁数で測る。

定義 1.1（ビット長, bit length）正の整数 $n$ の 2 進表示の桁数 $\ell(n) = \lfloor \log_2 n \rfloor + 1$ を $n$ のビット長という。$\ell(n) = k$、すなわち $2^{k-1} \leq n < 2^k$ のとき、$n$ を $k$ ビットの整数という。

計算の手間はビット演算 (bit operation)、すなわち 1 ビットどうしの論理演算の回数で測る（計算機が 64 ビット単位などで処理することは定数倍の違いにすぎない）。$f(k) = O(g(k))$ は、定数 $C$ があって十分大きいすべての $k$ で $f(k) \leq Cg(k)$ となることを表す。

定義 1.2（多項式時間, polynomial time）整数を入力とするアルゴリズムが多項式時間であるとは、入力のビット長の和を $L$ とするとき、ビット演算の回数が $O(L^c)$ となる定数 $c$ が存在することをいう。

例 1.3（試し割り）$n$ を $2, 3, \dots, \lfloor \sqrt{n} \rfloor$ で順に割って素因数を探す方法は、$n$ が同じくらいの大きさの 2 素数の積なら約 $\sqrt{n} \approx 2^{\ell(n)/2}$ 回の割り算を要し、$\ell(n)$ の指数関数である。$\ell(n) = 2048$ なら約 $2^{1024} \approx 1.8 \times 10^{308}$ 回で、毎秒 $10^{18}$ 回割れても約 $1.8 \times 10^{290}$ 秒かかる（宇宙の年齢は約 $4 \times 10^{17}$ 秒）。

命題 1.4（筆算の計算量）$a, b$ を正の整数、$k = \ell(a)$, $l = \ell(b)$ とする。

1. $a + b$ と $\lvert a - b \rvert$ は $O(\max(k, l))$ 回のビット演算で計算できる。
2. $ab$ は $O(kl)$ 回のビット演算で計算できる。
3. $a \geq b$ のとき、$a = qb + r$（$0 \leq r < b$）をみたす $q, r$ は $O(l \cdot \ell(q))$ 回のビット演算で計算できる。

証明. 2 進の筆算の手順を数える。(1) 下の桁から順に、その桁と繰り上がり（繰り下がり）を定数回の論理演算で求める。(2) $k \geq l$ としてよい。$b = \sum_j b_j 2^j$ なら $ab = \sum_{b_j = 1} 2^j a$ で、$k + l$ ビット以下の数を高々 $l$ 回足せばよいので、(1) より $O(l(k + l)) = O(kl)$。(3) $a < 2^k$, $b \geq 2^{l-1}$ より $q < 2^{k-l+1}$ である。筆算の割り算は $q$ のビットを上から 1 つずつ、$l + 1$ ビット以下の数の比較と引き算で決めるので、$O(l(k - l + 1))$ 回で済む。$k > l$ なら $a/b > 2^{k-1}/2^l$ より $\ell(q) \geq k - l$ で、$q \geq 1$ と合わせて $k - l + 1 \leq 2\ell(q)$ である。$\square$

特に $\mathbb{Z}/n\mathbb{Z}$ の積（積を $n$ で割った余り）は $O(\ell(n)^2)$ 回で計算できる（カラツバ法など、より速い掛け算の方法もある）。

1.2 反復二乗法

RSA では $a^e \bmod n$ を数千ビットの $e, n$ で計算する。$a$ を $e - 1$ 回掛けるのでは回数が天文学的になるが、指数を 2 進展開して 2 乗を繰り返せば $e$ の桁数程度の回数で済む。

反復二乗法（square-and-multiply）　入力は $n \geq 2$, $0 \leq a < n$, $e \geq 1$ で、$e = (e_{L-1} \cdots e_1 e_0)_2$（$L = \ell(e)$, $e_{L-1} = 1$）とする。$x \leftarrow a$ とし、$i = L - 2, \dots, 1, 0$ の順に「$x \leftarrow x^2 \bmod n$ とし、$e_i = 1$ ならさらに $x \leftarrow xa \bmod n$ とする」を行って、最後の $x$ を出力する。

定理 1.5（反復二乗法の計算量）反復二乗法は $a^e \bmod n$ を出力する。法 $n$ での乗算（2 乗を含む）の回数は $(\ell(e) - 1) + (w(e) - 1) \leq 2(\ell(e) - 1)$ である（$w(e)$ は $e$ の 2 進表示の $1$ の個数）。ビット演算の回数は $O(\ell(e)\ell(n)^2)$ であり、特に $1 \leq e < n$ なら $O(\ell(n)^3)$ である。

証明. $E_i = \lfloor e/2^i \rfloor$（上位のビット $e_{L-1} \cdots e_i$ が表す数）とおくと、$E_{L-1} = 1$, $E_0 = e$, $E_i = 2E_{i+1} + e_i$ である。添字 $i$ の処理後に $x \equiv a^{E_i} \pmod{n}$ となることを $i$ の降順の帰納法で示す。最初は $x = a = a^{E_{L-1}}$ で、添字 $i + 1$ で成り立てば、添字 $i$ の処理後の $x$ は $(a^{E_{i+1}})^2 a^{e_i} = a^{E_i}$ と合同である。よって出力は $a^{E_0} \bmod n = a^e \bmod n$。2 乗は $L - 1$ 回、$a$ を掛けるのは $i \leq L - 2$ かつ $e_i = 1$ となる $w(e) - 1$ 回である。各乗算は $n$ 未満の 2 数の積と、$n^2$ 未満の数の $n$ による割り算（商は $n$ 未満）なので、命題 1.4 より $O(\ell(n)^2)$ である。$e < n$ なら $\ell(e) \leq \ell(n)$。$\square$

例 1.6 $2^{560} \bmod 561$ を計算する。$560 = (1000110000)_2$ なので、2 乗 9 回と、$2$ を掛ける乗算 2 回で済む。

たとえば $256^2 = 65536 \equiv 460$, $460 \cdot 2 = 920 \equiv 359$、$67^2 = 4489 = 8 \cdot 561 + 1$ である。よって $2^{560} \equiv 1 \pmod{561}$ である（1.7 節で再び使う）。

1 回の乗算で指数の最大値は高々 2 倍にしかならないので、$a^e$ には少なくとも $\log_2 e$ 回の乗算が要り、定理 1.5 の回数は最小の 2 倍以内である。RSA でよく使われる $e = 65537 = 2^{16} + 1$ なら、2 乗 16 回と乗算 1 回で済む。

1.3 拡張ユークリッドの互除法

RSA の鍵生成では逆元 $d = e^{-1} \bmod \lambda(n)$（第2章）を計算する。04-algebra 第1章の例 1.25 の計算を、係数を同時に更新する形に整理して計算量を評価する。

拡張ユークリッドの互除法　入力は $a \geq b \geq 1$。$r_0 = a$, $r_1 = b$, $(s_0, t_0) = (1, 0)$, $(s_1, t_1) = (0, 1)$ とし、$i = 1, 2, \dots$ について $r_i \neq 0$ である間、$q_i = \lfloor r_{i-1}/r_i \rfloor$ として

と定める。$r_{m+1} = 0$ となったら止め、$(r_m, s_m, t_m)$ を出力する（$m$ は割り算の回数）。

定理 1.7（拡張ユークリッドの互除法, extended Euclidean algorithm）$a \geq b \geq 1$ とする。

1. $0 \leq i \leq m + 1$ で $s_i a + t_i b = r_i$ であり、$r_m = \gcd(a, b)$ である。特に $\gcd(a, b) = 1$ なら $t_m b \equiv 1 \pmod{a}$。
2. 割り算の回数は $m \leq 2\lfloor \log_2 b \rfloor + 1$ をみたす。
3. 全体のビット演算の回数は $O(\ell(a)^2)$ である。

証明. (1) $i = 0, 1$ では定義から成り立ち、$i - 1$ と $i$ で成り立てば漸化式から $i + 1$ でも成り立つ。$r_m = \gcd(a, b)$ は互除法の正しさ（04-algebra 第1章 補題 1.10）による。

(2) $1 \leq i \leq m$ のとき、$r_{i-1} \geq r_i > r_{i+1}$ より $q_i \geq 1$ で、$r_{i-1} = q_i r_i + r_{i+1} > 2r_{i+1}$。$r_1 = b$ から始めてこれを繰り返すと、$j \geq 0$ について $r_{2j+1} \leq b/2^j$ である。$m = 2j + 1$ なら $1 \leq r_m \leq b/2^j$、$m = 2j$（$j \geq 1$）なら $2 \leq r_{2j-1} \leq b/2^{j-1}$（$r_{2j-1} > r_{2j} \geq 1$ による）で、いずれも $2^j \leq b$、すなわち $j \leq \lfloor \log_2 b \rfloor$ となる。よって $m \leq 2j + 1 \leq 2\lfloor \log_2 b \rfloor + 1$。

(3) まず係数の大きさを抑える。$\lvert s_{i+1} \rvert \leq \lvert s_{i-1} \rvert + q_i\lvert s_i \rvert \leq (q_i + 1)\max(\lvert s_{i-1} \rvert, \lvert s_i \rvert)$ と $\max(\lvert s_0 \rvert, \lvert s_1 \rvert) = 1$ から、帰納法で $\lvert s_i \rvert \leq \prod_{1 \leq j < i}(q_j + 1) \leq \prod_{j=1}^m 2q_j$ を得る（$t$ も同様）。$r_{i-1} \geq q_i r_i$ より $\prod_{i=1}^m q_i \leq \prod_{i=1}^m r_{i-1}/r_i \leq a$ なので、$\lvert s_i \rvert, \lvert t_i \rvert \leq 2^m a$、すなわち係数のビット長は $m + \ell(a) = O(\ell(a))$ 以下である。第 $i$ 回の計算（割り算、$q_i s_i$ と $q_i t_i$、引き算）は命題 1.4 より $O(\ell(a)(\ell(q_i) + 1))$ 回でできる。

（最後は (2) による）なので、全体で $O(\ell(a)^2)$ である。$\square$

例 1.8 $17$ の法 $3120$ での逆元を求める（$a = 3120$, $b = 17$）。

$m = 4$ で、$2 \cdot 3120 - 367 \cdot 17 = 1$ より $17^{-1} \equiv -367 \equiv 2753 \pmod{3120}$。$3120 = (61 - 1)(53 - 1)$ なので、この $2753$ は第2章で RSA の法 $n = 61 \cdot 53 = 3233$ の秘密鍵として使う。

1.4 中国剰余定理による高速化

秘密鍵の持ち主は $n = pq$ の素因数を知っているので、冪剰余を半分の大きさの法での 2 つの計算に分けられる。

命題 1.9（中国剰余定理による冪剰余）$p, q$ を相異なる奇素数、$n = pq$ とし、正の整数 $d$ は $\gcd(d, p - 1) = \gcd(d, q - 1) = 1$ をみたすとする。整数 $c$ に対し、$d_p = d \bmod (p - 1)$, $d_q = d \bmod (q - 1)$, $m_p = c^{d_p} \bmod p$, $m_q = c^{d_q} \bmod q$, $q' = q^{-1} \bmod p$, $h = (m_p - m_q)q' \bmod p$ とおき、$m = m_q + qh$ とする。このとき $m = c^d \bmod n$ である。

証明. $p - 1 \geq 2$ と $\gcd(d, p - 1) = 1$ より $p - 1 \nmid d$ なので $d_p \geq 1$。$p \nmid c$ なら、$d = d_p + j(p - 1)$ とフェルマーの小定理（04-algebra 第1章 系 1.35）より $c^d \equiv c^{d_p} \pmod{p}$。$p \mid c$ なら $d, d_p \geq 1$ より両辺とも $0$ と合同。よって $c^d \equiv m_p \pmod{p}$、同様に $c^d \equiv m_q \pmod{q}$。一方 $m \equiv m_q \pmod{q}$, $m \equiv m_p \pmod{p}$, $0 \leq m \leq (q - 1) + q(p - 1) = n - 1$ なので、中国剰余定理（同 定理 1.28）の一意性より $m = c^d \bmod n$。$\square$

$\ell(n) = k$ で $d$ がランダムな $k$ ビットの数なら、定理 1.5 の乗算は約 $1.5k$ 回、1 回あたり $Ck^2$ 程度で全体で約 $1.5Ck^3$。命題 1.9 では法も指数も約 $k/2$ ビットの冪剰余 2 回で約 $2 \cdot 1.5C(k/2)^3 = 0.375Ck^3$ となり、筆算の評価で約 4 倍速い。多くの RSA の実装はこの方法を使っている。

例 1.10 $n = 3233 = 61 \cdot 53$, $d = 2753$（例 1.8）, $c = 2790$ とする。$d_p = 2753 \bmod 60 = 53$, $d_q = 2753 \bmod 52 = 49$、$c \bmod 61 = 45$, $c \bmod 53 = 34$ から $m_p = 45^{53} \bmod 61 = 4$, $m_q = 34^{49} \bmod 53 = 12$。$53^{-1} \bmod 61 = 38$ より $h = (4 - 12) \cdot 38 \bmod 61 = 1$ で、$m = 12 + 53 = 65$。実際 $65^{17} \equiv 2790 \pmod{3233}$ である（第2章の RSA の例）。

1.5 素数の分布

RSA の鍵には、たとえば 1024 ビットの素数が 2 つ必要である。$x$ 以下の素数の個数を $\pi(x)$ と書く。

定理 1.11（素数定理, prime number theorem）$\displaystyle\lim_{x \to \infty} \frac{\pi(x)}{x/\log x} = 1$（$\log$ は自然対数）。

1896 年にアダマールとド・ラ・ヴァレ・プーサンが独立に証明した（本教材では05-complex-analysis 第8章の定理 8.8）。実際の値（PARI/GP で計算）と比べると、比はゆっくり $1$ に近づく。

$k$ ビットの整数 $2^{k-1}$ 個のうち素数は $\pi(2^k) - \pi(2^{k-1})$ 個である。$\pi(x) \approx x/\log x$ を代入すると

となる。素数定理は極限の主張なので、これは定理ではなく目安だが、実際とよく合う（$k = 32$ では素数は $98182656$ 個で割合は $1/21.87$、目安は $1/22.18$）。目安によれば 1024 ビットの奇数の約 $1/355$ が素数であり、ランダムに試せばすぐに見つかる。

1.6 フェルマーテストとカーマイケル数

$n$ が素数なら、$n$ と互いに素なすべての $a$ で $a^{n-1} \equiv 1 \pmod{n}$ である。したがって $a^{n-1} \not\equiv 1 \pmod n$ となる $a$ が見つかれば、素因数を見つけないまま $n$ は合成数だと確定する（フェルマーテスト）。

定義 1.12（フェルマーの証人と偽証人）$n \geq 3$ を奇数、$a \in \lbrace 1, \dots, n - 1 \rbrace$ とする。$a^{n-1} \not\equiv 1 \pmod{n}$ のとき $a$ をフェルマーの証人 (Fermat witness) という。$n$ が合成数で $a^{n-1} \equiv 1 \pmod{n}$ のとき、$a$ をフェルマーの偽証人 (Fermat liar)、$n$ を底 $a$ の擬素数 (pseudoprime) という。

例 1.13 $341 = 11 \cdot 31$ は、$2^{10} = 1024 = 3 \cdot 341 + 1$ より $2^{340} = (2^{10})^{34} \equiv 1 \pmod{341}$ をみたし、底 $2$ の擬素数である（底 $2$ の擬素数の中で最小）。一方 $3^{340} \equiv 56 \pmod{341}$ なので、$3$ は証人である。

命題 1.14 $n \geq 3$ を奇数の合成数とし、$F = \lbrace a \in (\mathbb{Z}/n\mathbb{Z})^\times \mid a^{n-1} = 1 \rbrace$ とおく。$F$ は $(\mathbb{Z}/n\mathbb{Z})^\times$ の部分群で、フェルマーの偽証人の全体と一致する。$F \neq (\mathbb{Z}/n\mathbb{Z})^\times$ ならば偽証人は $\varphi(n)/2$ 個以下である。

証明. $a \mapsto a^{n-1}$ は可換群 $(\mathbb{Z}/n\mathbb{Z})^\times$ の準同型なので、その核 $F$ は部分群である。$a^{n-1} \equiv 1$ なら $a$ は逆元 $a^{n-2}$ をもつので、偽証人は単元に限り、$F$ に一致する。$F$ が真部分群なら、ラグランジュの定理（04-algebra 第2章 定理 2.29）より $\lvert F \rvert$ は $\varphi(n)$ の真の約数なので $\varphi(n)/2$ 以下である。$\square$

定義 1.15（カーマイケル数, Carmichael number）偽証人が単元のすべてになる合成数、すなわち合成数 $n$ で、$n$ と互いに素なすべての整数 $a$ について $a^{n-1} \equiv 1 \pmod{n}$ が成り立つものをカーマイケル数という。

$561 = 3 \cdot 11 \cdot 17$ はカーマイケル数である（04-algebra 第1章 注意 1.37）。

定理 1.16（コルセルトの判定法, Korselt's criterion）合成数 $n$ がカーマイケル数であるための必要十分条件は、$n$ が平方因子をもたず（どの素数 $p$ についても $p^2 \nmid n$）、$n$ の各素因数 $p$ について $p - 1 \mid n - 1$ となることである。

証明. 十分性：$\gcd(a, n) = 1$ とする。$n$ の各素因数 $p$ について、フェルマーの小定理と $p - 1 \mid n - 1$ より $a^{n-1} \equiv 1 \pmod{p}$。$n$ は相異なる素数の積なので、中国剰余定理より $a^{n-1} \equiv 1 \pmod{n}$。

必要性：$n$ をカーマイケル数とする。$p^2 \mid n$ となる素数 $p$ があったとし、$a = 1 + n/p$ とおく。$n$ の素因数はすべて $n/p$ を割るので $\gcd(a, n) = 1$。また $(n/p)^2 = n \cdot (n/p^2)$ は $n$ の倍数なので、二項展開により $a^{n-1} \equiv 1 + (n - 1)n/p \pmod{n}$。これが $1$ と合同なら $n \mid (n - 1)n/p$、すなわち $p \mid n - 1$ となるが、$p \mid n$ なので不可能である。よって $n$ は平方因子をもたない。次に $p$ を $n$ の素因数、$g$ を法 $p$ の原始根（04-algebra 第1章 定理 1.44）とする。$p$ と $n/p$ は互いに素なので、中国剰余定理により $a \equiv g \pmod{p}$, $a \equiv 1 \pmod{n/p}$ となる $a$ がとれる。すると $a^{n-1} \equiv 1 \pmod{n}$ より $g^{n-1} \equiv 1 \pmod{p}$ で、$g$ の位数は $p - 1$ なので $p - 1 \mid n - 1$（同 命題 1.40）。$\square$

系 1.17 カーマイケル数は奇数であり、相異なる素因数を少なくとも 3 個もつ。

証明. カーマイケル数 $n$ は平方因子をもたない合成数なので、相異なる 2 個以上の素数の積である。$n$ が偶数なら奇素因数 $p$ をもち、偶数 $p - 1$ が奇数 $n - 1$ を割ることになり矛盾する。$n = pq$（$p < q$）なら、$n - 1 = p(q - 1) + (p - 1)$ より $q - 1 \mid p - 1$ だが、$0 < p - 1 < q - 1$ なので矛盾する。$\square$

例 1.18 $1105 = 5 \cdot 13 \cdot 17$（$1104$ は $4, 12, 16$ の倍数）、$1729 = 7 \cdot 13 \cdot 19$（$1728$ は $6, 12, 18$ の倍数）もカーマイケル数である。計算機で調べると、$10^4$ 未満のカーマイケル数は $561, 1105, 1729, 2465, 2821, 6601, 8911$ の 7 個、$10^6$ 未満では 43 個である。数は少ないが無限に存在する（アルフォード・グランヴィル・ポメランス、1994 年。主張のみ）。

カーマイケル数をフェルマーテストで見抜けるのは $n$ と互いに素でない $a$ を引いたときだけである。その確率は $1 - \varphi(n)/n$ 未満で、素因数がどれも大きければきわめて小さい。

1.7 ミラー–ラビン法

フェルマーテストを強化する鍵は、「法が素数なら $1$ の平方根は $\pm 1$ しかない」という事実である。

補題 1.19（1 の非自明な平方根）$n \geq 3$, $x^2 \equiv 1 \pmod{n}$, $x \not\equiv \pm 1 \pmod{n}$ ならば、$\gcd(x - 1, n)$ は $n$ の $1$ でも $n$ でもない約数である。特に $n$ が素数なら、$x^2 \equiv 1 \pmod{n}$ の解は $x \equiv \pm 1$ に限る。

証明. $n \mid (x - 1)(x + 1)$ である。$\gcd(x - 1, n) = n$ なら $x \equiv 1$。$\gcd(x - 1, n) = 1$ なら04-algebra 第1章の命題 1.9 より $n \mid x + 1$ で $x \equiv -1$。いずれも仮定に反する。素数 $n$ の正の約数は $1$ と $n$ だけなので、後半も従う。$\square$

以下、$n \geq 3$ を奇数とし、$n - 1 = 2^s t$（$s \geq 1$, $t$ は奇数）と書く。

定義 1.20（強い証人と強い偽証人）$a \in \lbrace 1, \dots, n - 1 \rbrace$ が

$$a^t \equiv 1 \pmod{n} \quad \text{または} \quad a^{2^i t} \equiv -1 \pmod{n}\ \ (\text{ある}\ 0 \leq i \leq s - 1)$$

をみたすとき、$a$ は $n$ の強い検定に合格するという。合格しない $a$ を強い証人 (strong witness) という。$n$ が合成数で $a$ が合格するとき、$a$ を強い偽証人 (strong liar)、$n$ を底 $a$ の強擬素数 (strong pseudoprime) という。

命題 1.21 $n$ が奇素数なら、すべての $a \in \lbrace 1, \dots, n - 1 \rbrace$ は強い検定に合格する。したがって強い証人が 1 つでもあれば $n$ は合成数である。

証明. 列 $a^t, a^{2t}, \dots, a^{2^s t} = a^{n-1}$ の最後の項はフェルマーの小定理より $1$ と合同である。$a^t \not\equiv 1$ なら、$a^{2^j t} \equiv 1$ となる最小の $j$（$1 \leq j \leq s$）について $x = a^{2^{j-1}t}$ は $x^2 \equiv 1$, $x \not\equiv 1$ をみたすので、補題 1.19 より $x \equiv -1$ であり、$i = j - 1$ として合格する。$\square$

例 1.22 (1) $n = 561$, $a = 2$ のとき、$560 = 2^4 \cdot 35$ で、例 1.6 の表から列 $2^{35}, 2^{70}, 2^{140}, 2^{280}$ は $263, 166, 67, 1$ である。$67^2 \equiv 1$ だが $67 \not\equiv \pm 1$ なので $2$ は強い証人であり、フェルマーテストでは見抜けなかったカーマイケル数が同じ計算の途中経過から見抜けた。補題 1.19 より約数 $\gcd(66, 561) = 33$ まで得られる。(2) $n = 2047 = 23 \cdot 89$ のとき、$2046 = 2 \cdot 1023$ で、$2^{11} = 2048 \equiv 1$ より $2^{1023} = (2^{11})^{93} \equiv 1$ なので、$2$ は強い偽証人である。これは底 $2$ の強擬素数の中で最小で、底を固定した判定はだまされうる。

ミラー–ラビン法（Miller–Rabin test）　ミラー（1976 年）が一般化リーマン予想のもとで考えた決定的な判定法を、ラビン（1980 年）が底をランダムに選ぶ確率的な判定法に作り替えたものである。入力は奇数 $n \geq 5$ と反復回数 $r$。$\lbrace 2, \dots, n - 2 \rbrace$ から $a$ を一様ランダムに選んで強い検定を行うことを $r$ 回繰り返し、一度でも強い証人が出れば「合成数」、出なければ「おそらく素数」と出力する。

1 回の検定は定理 1.5 より $O(\ell(n)^3)$ でできる。命題 1.21 より素数が「合成数」と判定されることはなく、合成数を誤る確率は次の定理で抑えられる。