整数論と合同式：ステップごとの解答つき練習問題

1余りと合同式

a を n で割ると、商 q と余り r が得られます：a = q·n + r、0 ≤ r < n。余りは a mod n と書きます。負の数では q も負になります：−3 = −1·7 + 4 なので、−3 mod 7 = 4 です。

2 つの数は、同じ余りをもつとき、つまり n が a − b を割り切るとき、n を法として合同であるといい、a ≡ b (mod n) と書きます。

余りはステップごとに簡約でき、数を小さく保てます：

たとえば 47·58 mod 9 では、47 ≡ 2、58 ≡ 4 なので、47·58 ≡ 8 (mod 9) です。

2ユークリッドの互除法

最大公約数 gcd(a, b) は、両方を割り切る最大の数です。ユークリッドの互除法は gcd(a, b) = gcd(b, a mod b) を使います：

1. 割ります：a = q·b + r。
2. (a, b) を (b, r) に置き換えます。
3. 余りが 0 になるまで繰り返します。最後の 0 でない余りが gcd です。

最小公倍数はそこから求まります：lcm(a, b) = a·b / gcd(a, b)。

3逆元と拡張ユークリッドの互除法

n を法とする a の逆元は、a·x ≡ 1 (mod n) を満たす数 x です。gcd(a, n) = 1 のときに限って存在します。

拡張ユークリッドの互除法は、(n, a) にユークリッドの互除法を適用し、各余りに係数 t を記録して、すべての余り r が r ≡ t·a (mod n) を満たすようにします。n に t = 0、a に t = 1 を割り当てて始め、新しい t は、2 行上の t から、商 q に 1 行上の t を掛けたものを引いて求めます。余り 1 が現れたら、その t が逆元です。

逆元があれば、合同式 a·x ≡ b (mod n) は x ≡ a⁻¹·b で解けます。d = gcd(a, n) が 1 より大きいとき、d が b を割り切るなら解は d 個あり、そうでなければ解はありません。

法が互いに素な 2 つの合同式 x ≡ r₁ (mod m₁) と x ≡ r₂ (mod m₂) には、m₁·m₂ を法としてちょうど 1 つの解があります（中国の剰余定理）。x = r₁ + m₁k とおいて k を求めます。

4冪剰余と RSA

反復二乗法を使うと aᵏ mod n を速く計算できます：k を 2 進数で書き、a, a², a⁴, a⁸, … mod n を二乗と簡約で求め、ビットが 1 のものの冪を掛けます。

フェルマーの小定理：素数 p が a を割り切らないとき、aᵖ⁻¹ ≡ 1 (mod p) です。したがって指数は p − 1 を法として簡約できます。

RSA は、2 つの素数 p と q から鍵をつくります：

1. n = p·q、φ(n) = (p − 1)(q − 1)。
2. gcd(e, φ(n)) = 1 となる e を選びます。(n, e) が公開鍵です。
3. d = e⁻¹ mod φ(n) を計算します：これが秘密鍵です。
4. 暗号化は c = mᵉ mod n、復号は m = cᵈ mod n です。

オイラーの φ(n) は、1 から n までの数のうち n と互いに素なものの個数です：素数なら φ(p) = p − 1、φ(pᵏ) = pᵏ − pᵏ⁻¹ で、互いに素な因数については φ は乗法的です。

5よくある間違い

• 負の数の余りを負で答えてしまう：−17 mod 5 は −2 ではなく 3 です。
• ユークリッドの互除法を、最後の 0 でない余りではなく最初の余りで止めてしまう。
• 拡張ユークリッドの互除法で出た負の係数に、n を足し忘れる。
• RSA の指数 d を、φ(n) ではなく n を法として計算してしまう。
• フェルマーの小定理で、指数を p − 1 ではなく p を法として簡約してしまう。

6試験問題の例

• やさしい：gcd と余り。ユークリッドの互除法で gcd や lcm を求める、負の数の余りを求める、和と積を n を法として簡約する、といった問題です。
• ふつう：逆元と合同式。拡張ユークリッドの互除法で 剰余の逆元を求める、一次合同式を解く、中国の剰余定理で 2 つの合同式を組み合わせる、オイラーの φ(n) を計算する、といった問題です。
• むずかしい：冪剰余と RSA。反復二乗法とフェルマーの小定理を使う、解が複数ある合同式を解く、RSA の秘密指数・暗号文・復号したメッセージを求める、といった問題です。