Chapter 01

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

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

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

• コンピュータが扱う数は有限だから。8 ビットなら 0〜255 しかなく、256 を足せば 0 に戻る。 この「戻る」を数学として正面から扱うのが合同算術である。
• 有限だからこそ「逆算が難しい」現象が起きるから。これが暗号の安全性の源になる。

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

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}\)）と書く。 実用上は各グループの代表として\(\{0, 1, 2, \dots, m-1\}\)を使えばよい。

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

「合同」が本当に「同じ仲間」と呼ぶに値するか、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\)が存在するから。 ところが法 12 の世界には「2 を掛けたら 1 になる数」が存在しない。 \(2 \times 0, 2\times 1, \dots, 2 \times 11\)を全部計算しても、結果は偶数（0,2,4,…,10）にしかならず、1 は出てこない。

つまり割り算ができるかどうかは、「逆元」が存在するかどうかにかかっている。次節でその条件を突き止める。

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\)と答えが出る。 巨大な数でも驚くほど速く終わる（後述）。

実例: 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 ステップで、数は少なくとも半分以下になる。

導出: \(a = qb + r\)（\(0 \le r < b\)）とする。

• \(r < b/2\)ならその時点で半分以下。
• \(r \geq b/2\)なら、次のステップの余り\(r'\)は\(b = 1 \cdot r + r'\)（\(b < 2r\)なので商は 1）より\(r' = b - r \le b - b/2 = b/2\)。

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

したがってステップ数は\(O(\log \min(a,b))\)。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\)）のとき:

この更新式が正しい理由: 帰納法。\(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)\)を与える。

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)\)を拡張ユークリッドで:

（\(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}\)で見ると\(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 回掛けるのは無駄が多い。

アルゴリズム

指数を 2 進数で見て、「2 乗する」と「掛ける」だけで到達する:

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

導出（正しさ）

指数\(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}\)回の掛け算が必要で、 宇宙の年齢でも終わらない。繰り返し二乗法なら約 2048 回。この差が実用と非実用を分けている。

7. まとめ