Chapter 01

合同算術とユークリッドの互除法

この章で手に入るもの. これから先、暗号も誤り訂正も「有限個の数しかない世界」で計算する。 無限に続く数直線ではなく、時計の文字盤のようにぐるっと回って戻ってくる数の世界である。

なぜそんな世界を使うのか。理由は 2 つある。

• コンピュータが扱う数は有限だから。コンピュータは 0 か 1 の 1 桁（ビット）を並べて数を表す。8 ビットなら\(2^8 = 256\)通り、つまり 0〜255 しかなく、255 に 1 を足すと 0 に戻る。 この「戻る」を数学として正面から扱うのが合同算術である。
• 有限だからこそ「逆算が難しい」現象が起きるから。これが暗号の安全性の源になる。

この章では、その世界の足し算・引き算・掛け算、そして一番の難所である割り算（逆元）を作る。 割り算を作る道具が、紀元前 300 年から知られているユークリッドの互除法である。

記号の約束: 以下、導出の終わりに ∎、条件が満たされたことの確認に ✓ を付ける。また「2048 ビットの数」のように言うときは、\(2^{2048}\)（10 進で約 617 桁）程度の大きさの整数を指す。

1. 合同とは — 時計の算数

定義

整数\(a, b\)と正整数\(m\)について、\(a - b\)が\(m\)で割り切れるとき、 \(a\)と\(b\)は法\(m\)の下で合同であるといい、次のように書く:

（読み方は「\(a\) 合同 \(b\) モッド \(m\)」。\(m\)を法 (modulus) と呼ぶ。）

直感: 時計の文字盤

いま 10 時だとする。5 時間後は何時か。\(10 + 5 = 15\) だが、時計は 12 で一周するので3 時である。 このとき

が成り立っている。\(15 - 3 = 12\) が 12 で割り切れるからである。

つまり合同とは「12 で割った余りが同じ」ということ。時計の文字盤の上では 15 も 3 も同じ場所を指す。

言い換えると. 法\(m\)の世界では、整数は\(m\)個のグループに分類される。 \(m = 12\)なら、\(\{\dots, -12, 0, 12, 24, \dots\}\)、\(\{\dots, -11, 1, 13, 25, \dots\}\)、…という 12 個のグループ。 このグループを剰余類と呼び、グループ全体の集合を\(\mathbb{Z}_m\)（または\(\mathbb{Z}/m\mathbb{Z}\)）と書く。 同じグループの数は法\(m\)の計算ではまったく区別がつかないので、各グループから 1 つずつ数を選んで（代表）、それで計算すればよい。 実用上は「\(m\)で割った余り」\(\{0, 1, 2, \dots, m-1\}\)を代表に使う（各グループにちょうど 1 つずつ含まれ、一番小さい非負の数だから）。

2 種類の「mod」の書き方. この文書群では次の 2 つを使い分ける。

• \(a \equiv b \pmod m\): 上で定義した関係（\(a\)と\(b\)は法\(m\)で合同）。式全体にかかる。
• \(a \bmod m\): 演算。\(a\)を\(m\)で割った余り（\(0\)以上\(m\)未満の整数）を表す。たとえば\(15 \bmod 12 = 3\)。

両者の関係は「\(a \equiv b \pmod m\) \(\iff\) \(a \bmod m = b \bmod m\)」である。

同値関係であることの確認

「同じ仲間」という分類が破綻しないためには、関係が次の 3 条件を満たす必要がある（この 3 条件を満たす関係を同値関係と呼ぶ。 同値関係があれば、集合を「互いに関係のあるものどうし」のグループに重なりなく分けられる）。「合同」がこれを満たすことを確かめる:

• 反射律 \(a \equiv a\): \(a - a = 0\)は\(m\)で割り切れる ✓
• 対称律 \(a \equiv b \Rightarrow b \equiv a\): \(a-b\)が\(m\)の倍数なら\(b-a = -(a-b)\)も\(m\)の倍数 ✓
• 推移律 \(a \equiv b, b \equiv c \Rightarrow a \equiv c\): \(a-b = mk\)、\(b-c = ml\)なら\(a-c = m(k+l)\) ✓

∎ よって合同は同値関係であり、整数を綺麗に分類する。

2. 合同式の演算 — 足し算・引き算・掛け算は「そのまま」できる

定理

\(a \equiv b \pmod m\)、\(c \equiv d \pmod m\)のとき:

導出

仮定より\(a - b = m k\)、\(c - d = m l\)（\(k, l\)は整数）と書ける。

足し算: \((a+c) - (b+d) = (a-b) + (c-d) = m(k+l)\)。\(m\)の倍数なので合同 ✓

引き算: \((a-c) - (b-d) = (a-b) - (c-d) = m(k-l)\) ✓

掛け算: ここだけ少し工夫する。\(a = b + mk\)、\(c = d + ml\)を代入して展開:

よって\(ac - bd = m(bl + dk + mkl)\)は\(m\)の倍数 ✓ ∎

この定理の実用上の意味: 計算途中でいつでも余りを取ってよい. たとえば\(123 \times 456 \bmod 7\)を計算したいとき、 馬鹿正直に\(123 \times 456 = 56088\)を計算してから 7 で割る必要はない。 先に\(123 \equiv 4\)、\(456 \equiv 1 \pmod 7\)と小さくしてから\(4 \times 1 = 4\)としてよい。 暗号では 2048 ビットの巨大数を何百回も掛けるので、この性質が無いと計算が破綻する。

注意: 割り算だけは「そのまま」できない

足し算・引き算・掛け算は素直に成り立つのに、割り算だけは事情が違う。

\(\pmod{12}\)で考える。\(2 \times 3 = 6\)、\(2 \times 9 = 18 \equiv 6\)。つまり

だが、両辺を\(2\)で「割って」\(3 \equiv 9\)としてはいけない（\(3 - 9 = -6\)は 12 の倍数ではない）。

なぜこうなるのか. 普通の数の世界で\(2x = 2y \Rightarrow x = y\)が言えるのは、\(2\)に逆数\(1/2\)（掛けると 1 になる相手）が存在するから。 ところが法 12 の世界には「2 を掛けたら 1 になる数」が存在しない。 \(2 \times 0, 2\times 1, \dots, 2 \times 11\)を全部計算しても、結果は偶数（0,2,4,…,10）にしかならず、1 は出てこない。

つまり割り算ができるかどうかは、「逆元」が存在するかどうかにかかっている。 逆元とは「掛けると 1 になる相手」のことで、法\(m\)の世界での逆数に当たる（5 節 で正式に定義する。それまでは「逆数」と同じ意味と思ってよい）。 3 節・4 節 でその存在条件と求め方の道具を作り、5 節 で仕上げる。

3. 最大公約数とユークリッドの互除法

逆元の話に入る前に、道具を 1 つ用意する。

最大公約数 (GCD)

\(a\)と\(b\)の両方を割り切る最大の正整数を最大公約数といい\(\gcd(a,b)\)と書く。

ユークリッドの互除法

\(\gcd(a, b)\)を求めるのに、素因数分解は要らない。次の 1 行の性質だけで十分である。

補題: \(a = qb + r\)（\(q\)は商、\(r\)は余り）のとき

導出: \(d\)を\(a\)と\(b\)の公約数とする。\(r = a - qb\)であり、右辺は\(d\)の倍数どうしの引き算なので\(r\)も\(d\)の倍数。 つまり\(a,b\)の公約数は必ず\(b,r\)の公約数。 逆に\(d'\)を\(b\)と\(r\)の公約数とすると、\(a = qb + r\)より\(a\)も\(d'\)の倍数なので、 \(b,r\)の公約数は必ず\(a,b\)の公約数。 両者の公約数の集合が完全に一致するので、その最大値も一致する ✓ ∎

なぜこれが嬉しいのか. \(r < b\)なので、この操作を繰り返すたびに数が必ず小さくなる。 小さくなり続ければいつか\(r = 0\)になり、そこで\(\gcd(b, 0) = b\)と答えが出る （\(0 = b \times 0\)なので\(0\)は\(b\)で割り切れる。よって\(b\)と\(0\)の公約数は\(b\)の約数すべてで、その最大は\(b\)自身）。 巨大な数でも驚くほど速く終わる（後述）。

実例: gcd(1071, 462)

余りが 0 になった 1 つ前の除数が答え: \(\gcd(1071, 462) = 21\)。

素因数分解（\(1071 = 3 \times 3 \times 7 \times 17\), \(462 = 2\times 3\times 7\times 11\)）をしなくても、 たった 3 回の割り算で求まった。

計算量: なぜ速いのか

主張: 互除法を 2 ステップ進めると、余りは 2 ステップ前の除数\(b\)の半分以下になる（\(r' \le b/2\)）。

導出: 1 ステップ目を\(a = qb + r\)（\(0 \le r < b\)）、2 ステップ目を\(b = q' r + r'\)（\(0 \le r' < r\)）とする。

• \(r < b/2\)なら、\(r' < r < b/2\)で主張が成り立つ。
• \(r \geq b/2\)なら、\(b < 2r\)なので 2 ステップ目の商は\(q' = 1\)、よって\(r' = b - r \le b - b/2 = b/2\)。

いずれにせよ 2 ステップで半減する ∎

したがって、数の大きさが\(\min(a,b)\)から 1 になるまでに半減を繰り返す回数は\(\log_2 \min(a,b)\)程度で、ステップ数はその 2 倍以内。 これを\(O(\log \min(a,b))\)と書く（\(O(f)\)は「\(f\)に比例する程度の量」の意味。定数倍は無視する）。2048 ビットの数でも数千回の割り算で終わる。 暗号が実用になる理由の一端がここにある。

4. 拡張ユークリッドの互除法 — 逆元を作る道具

ベズーの等式

定理: 任意の整数\(a, b\)（ともに 0 でない）に対し、次を満たす整数\(x, y\)が存在する:

なぜこれが逆元の話につながるのか（先に見取り図）. いま\(\gcd(a, m) = 1\)（互いに素）だとする。するとベズーの等式より

$$ax + my = 1$$

を満たす\(x, y\)がある。この式を\(\pmod m\)で見ると、\(my\)は\(m\)の倍数なので消えて

$$ax \equiv 1 \pmod m$$

つまり \(x\)こそが\(a\)の逆元である。 だから「\(x, y\)を実際に求める手続き」さえ作れば、逆元が計算できることになる。それが拡張ユークリッドである。

導出（互除法を逆にたどる）

実例で見る。\(\gcd(1071, 462) = 21\)の計算を、余りについて解いた形で書き直す:

下の式に上の式を代入して\(147\)を消す:

検算: \(-3 \times 1071 + 7\times 462 = -3213 + 3234 = 21\) ✓

つまり\(x = -3, y = 7\)。このように互除法の各ステップを逆順に代入していけば、必ず\(x, y\)が求まる ∎

漸化式による定式化（実装向け）

毎回代入をさかのぼるのは面倒なので、行きがけに係数も一緒に更新する方式にする。 \(r_i = a x_i + b y_i\)という形を保ちながら進む:

\(r_{i-1} = q_i r_i + r_{i+1}\)（すなわち\(r_{i+1} = r_{i-1} - q_i r_i\)。\(q_i\)は「\(r_{i-1}\)を\(r_i\)で割った商」で、これで次の\(r_{i+1}\)が決まる）のとき:

この更新式が正しい理由: 帰納法。\(r_{i-1} = ax_{i-1} + by_{i-1}\)と\(r_i = ax_i + by_i\)を仮定すると

となり、確かに\(r_{i+1} = ax_{i+1} + by_{i+1}\)の形が保たれる ✓ ∎

\(r\)が 0 になったとき、1 つ前の\((r_i, x_i, y_i)\)が\((\gcd, x, y)\)を与える。

実例: 同じ gcd(1071, 462) を「行きがけ」に解く

漸化式が何をしているかは、各余りを\(a, b\)の式のまま持ち歩くと一目で分かる。 \(a = 1071\)、\(b = 462\)とおき、余りを数値ではなく\(a, b\)の 1 次式として書き続ける:

（商は順に\(q_1 = 2, q_2 = 3, q_3 = 7\)。）数値で確かめると \(-3 \times 1071 + 7 \times 462 = -3213 + 3234 = 21\)、 \(22 \times 1071 - 51 \times 462 = 23562 - 23562 = 0\) ✓

各行の右辺を見ると、\(a\)の係数が\(x_i\)、\(b\)の係数が\(y_i\)になっている。 つまり「\(x_{i+1} = x_{i-1} - q_i x_i\)」という更新式は、この代入計算の係数だけを取り出したものにすぎない。 表にすると:

（表の読み方: \(i\)行目の\(q_i\)は\(r_{i-1} \div r_i\)の商で、これを使って次の行\(i+1\)の\(r_{i+1}, x_{i+1}, y_{i+1}\)を計算する。）

余りが 0 になった行の 1 つ前、\(i = 3\)の行がベズーの等式を与える:

「逆にたどる」方法と答えは同じ（\(x = -3, y = 7\)）だが、こちらは過去の式を覚えておく必要がなく、割り算と同時に 2 つの係数を更新するだけで済む。 実装はこの形で行う。

おまけ: 最後の行の係数にも意味がある. \(r_4 = 0\)の行の\(22a - 51b = 0\)は、 \(1071/462 = 51/22\)、つまり\(a/\gcd = 51\)、\(b/\gcd = 22\) を表している。 拡張ユークリッドは、副産物として分数の約分まで済ませている。

5. 乗法逆元 — 割り算の正体

定義と存在条件

定義: \(ax \equiv 1 \pmod m\)を満たす\(x\)を、\(a\)の法\(m\)における乗法逆元といい\(a^{-1}\)と書く。

定理: \(a\)の逆元が存在する \(\iff\) \(\gcd(a, m) = 1\)（\(a\)と\(m\)が互いに素）

導出:

（\(\Leftarrow\)）\(\gcd(a,m)=1\)なら、ベズーの等式より\(ax + my = 1\)なる\(x,y\)が存在。 \(\pmod m\)を取れば\(ax \equiv 1\)。よって\(x\)が逆元 ✓

（\(\Rightarrow\)）逆元\(x\)が存在するとする。\(ax \equiv 1 \pmod m\)は、ある整数\(k\)を使って\(ax - 1 = mk\)、 すなわち\(ax - mk = 1\)と書ける。 ここで\(d = \gcd(a,m)\)とおくと、左辺は\(d\)の倍数どうしの引き算なので\(d\)の倍数。 右辺は 1 なので、\(d\)は 1 の約数、つまり\(d = 1\) ✓ ∎

さっきの謎が解けた. 法 12 で 2 が割り算できなかったのは、\(\gcd(2, 12) = 2 \neq 1\)だったから。 逆に法 12 で逆元を持つのは\(\{1, 5, 7, 11\}\)（12 と互いに素な数）だけである。

ここで重要な観察: もし法\(m\)が素数なら、\(1\)から\(m-1\)までのすべての数が\(m\)と互いに素になる。 つまり0 以外のすべての要素が逆元を持つ = 割り算が自由にできる。 この「素数を法にすると四則演算が完全になる」という事実が、次章以降の有限体の出発点である。

実例: 法 26 における 7 の逆元（シーザー暗号の拡張で使う）

\(\gcd(7, 26)\)を拡張ユークリッドで。上の表と同じ手順だが、ここでは\(r_0 = 26\)（法\(m\)）、\(r_1 = 7\)（逆元を求めたい\(a\)）と大きいほうを先に置く。 すると\(r_i = 26 x_i + 7 y_i\)の形を保つので、\(a = 7\)の係数は\(y_i\)の側に出る（4 節 の見取り図\(ax + my = 1\)の\(x\)に当たるのが、この表では\(y\)）:

（\(x_2 = x_0 - q_1 x_1 = 1 - 3\cdot 0 = 1\)、\(y_2 = y_0 - q_1 y_1 = 0 - 3\cdot 1 = -3\)、以下同様。）

\(r_4 = 1\)なので\(\gcd = 1\)、そして\(26 \times 3 + 7 \times (-11) = 78 - 77 = 1\) ✓

\(\pmod{26}\)で見ると\(26 \times 3\)は消えて\(7 \times (-11) \equiv 1\)。\(-11 \equiv 15 \pmod{26}\)なので:

検算: \(7 \times 15 = 105 = 4\times 26 + 1 \equiv 1 \pmod{26}\) ✓

6. 繰り返し二乗法 — 巨大なべき乗を現実的な時間で

暗号では\(a^{65537} \bmod n\)のような計算が日常的に現れる。素直に 65537 回掛けるのは無駄が多い。

この節では、求めたい量を一般に

と書く。上の例なら\(e = 65537\)である。以下「\(e\)」はつねにこの指数を指す（法をこの節だけ\(m\)でなく\(n\)と書くのは RSA の慣例に合わせたためで、意味は同じ）。

アルゴリズム

指数\(e\)を 2 進数で見る。\(13 = 8 + 4 + 1 = 1\cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\)なので、2 進法では\(1101_2\)と書く（添字の 2 が「2 進」の印。左が上位桁）。 「2 乗する」と「掛ける」だけで到達する。\(e = 13\)なら:

\(a^1 \to a^2 \to a^4 \to a^8\)は 2 乗を 3 回するだけで作れるので、 掛け算の総回数は\(O(\log e)\)。\(65537 = 2^{16} + 1\)なら16 回の 2 乗 + 1 回の掛け算 = 17 回で済む。

どこが速くなっているのか

素直に計算すると、\(a^e\)は\(a\)を\(e\)個掛け合わせたもの（\(a \times a \times \cdots \times a\)、\(a\)が\(e\)個）なので、掛け算の記号は\(e-1\)個、つまり掛け算\(e - 1\)回。 指数が 1 増えるたびに掛け算が 1 回要る——指数は足し算でしか伸びない。

ところが 2 乗という操作は、掛け算 1 回で指数を 2 倍にする:

掛け算\(k\)回で指数が\(2^k\)に達する。指数が掛け算で伸びるので、指数が目標の\(e\)に届くまでの 2 乗の回数は\(\log_2 e\)で済む。 こうして作った\(a^{2^i}\)のうち、\(e\)の 2 進表示で 1 が立っている桁のものだけを掛け合わせれば\(a^e\)になる。 その掛け算も最大\(\log_2 e\)回なので、合計は\(2\log_2 e\)回以下である。

数値で追う: \(3^{13} \bmod 17\)

まず 2 乗を繰り返して\(3^{2^i} \bmod 17\)を作る（毎回 17 で余りを取る）:

\(13 = 8 + 4 + 1 = 1101_2\)なので、必要なのは\(3^8, 3^4, 3^1\)の 3 つ:

まず\(16 \times 13 = 208 = 12 \times 17 + 4 \equiv 4\)、次に\(4 \times 3 = 12\)。よって\(3^{13} \equiv 12 \pmod{17}\)。 検算: \(3^{13} = 1594323 = 93783 \times 17 + 12\) ✓

素直にやれば 12 回の掛け算のところを、2 乗 3 回 + 掛け算 2 回 = 5 回で済んだ。 しかも途中に現れる数は\(16^2 = 256\)を超えない。

速くなっている場所は 2 つある.

1. 回数: 指数を「足し算で伸ばす」のをやめて「2 倍ずつ伸ばす」ので、掛け算の回数が\(e\)回から\(\log_2 e\)回の桁に落ちる。
2. 桁数: 毎回\(\bmod n\)を取るので、掛け算に使う数はつねに\(n\)未満に収まる。 もし余りを取らずに\(3^{13}\)のような値をそのまま作ると、\(a^e\)の桁数は\(e\)に比例して膨れ上がり、 1 回の掛け算自体が重くなる。RSA の\(a^e\)を余りなしで書き下せば、桁数だけで宇宙の原子数を超える。

この 2 つが揃って初めて、2048 ビットのべき乗が「数千回の、固定長の掛け算」に化ける。

導出（正しさ）

指数\(e\)を 2 進展開して\(e = \sum_{i} b_i 2^i\)（\(b_i \in \{0,1\}\)）と書くと、指数法則より

\(a^{2^{i+1}} = (a^{2^i})^2\)なので、\(a^{2^i}\)は前の値の 2 乗で順に作れる ∎

各ステップで\(\bmod n\)を取れば（2 節 の定理により正当）、途中の数が巨大化することもない。

これが無いと RSA は動かない. 2048 ビットの指数を素直に扱えば\(2^{2048}\)回の掛け算が必要で、 宇宙の年齢でも終わらない。繰り返し二乗法なら多くとも 4096 回。この差が実用と非実用を分けている。

7. まとめ