理論計算機科学を読むための数学・証明・アルゴリズム基礎

第11章 数論・代数の基礎

章間ナビゲーション

この章で使う記号

記号 意味
a | b a が b を割り切る
gcd(a,b) a と b の最大公約数
a ≡ b (mod n) a と b が n を法として合同
[a]_n n を法とした剰余類
Z_n n を法とする剰余類の集合
x^{-1} 乗法逆元
G = <g> g が生成する巡回群
F_p 素数 p 個の元を持つ有限体

この章で解消する詰まりどころ

暗号理論では、次のような記法が頻繁に出ます。

a ≡ b (mod n)
gcd(a,b)
x^{-1} mod n
G = <g>
F_p

RSA、Diffie-Hellman、ElGamal、楕円曲線暗号を読むには、巨大な抽象代数は不要ですが、剰余計算、逆元、群、体の最小限は必要です。この章では、暗号の入口を読める状態を作ります。

本体教科書で使う箇所

  • 暗号理論: RSA、Diffie-Hellman、ElGamal、楕円曲線暗号。
  • 情報理論: 有限体上の符号、線形符号。
  • 計算複雑性: 数論的問題、素因数分解、離散対数問題。
  • アルゴリズム: Euclidの互除法、拡張Euclid法、モジュラ計算。

1. 整数と割り切り

整数 a が整数 b を割り切るとは、ある整数 k が存在して

b = ak

と書けることです。このとき a | b と書きます。

例:

3 | 12        12 = 3・4
5 ∤ 12        12 = 5k となる整数 k はない

2. 割り算の定理

任意の整数 a と正の整数 n に対して、整数 q と r が一意に存在し、

a = qn + r
0 ≤ r < n

を満たします。r を a を n で割った余りと呼びます。

例:

29 = 5・5 + 4
29 mod 5 = 4

3. 最大公約数

a と b の最大公約数を gcd(a,b) と書きます。

例:

gcd(84,30) = 6

最大公約数は、Euclidの互除法で効率よく計算できます。

gcd(a,b) = gcd(b, a mod b)

ただし b=0 なら gcd(a,0)=|a| です。

Euclidの互除法の例

gcd(84,30)
= gcd(30,24)
= gcd(24,6)
= gcd(6,0)
= 6

4. Bézout等式

d = gcd(a,b) とすると、ある整数 x, y が存在して、

ax + by = d

が成り立ちます。これを Bézout 等式と呼びます。

特に gcd(a,b)=1 のとき、

ax + by = 1

です。この事実は、モジュラ逆元の存在判定に使います。

5. 合同算術

整数 a, b が n を法として合同であるとは、n | (a-b) が成り立つことです。

a ≡ b (mod n)

例:

17 ≡ 2 (mod 5)

なぜなら 17 - 2 = 15 は5で割り切れるからです。

合同は「同じ余りを持つ」と考えてよいです。

6. 剰余類

mod n では、整数全体を余りごとのクラスに分けます。

例: mod 5 の剰余類。

[0] = {..., -10, -5, 0, 5, 10, ...}
[1] = {..., -9, -4, 1, 6, 11, ...}
[2] = {..., -8, -3, 2, 7, 12, ...}
[3] = {..., -7, -2, 3, 8, 13, ...}
[4] = {..., -6, -1, 4, 9, 14, ...}

mod n の世界では、これらのクラスを要素のように扱います。

7. mod n における演算

合同は加算・乗算と相性がよいです。

a ≡ b (mod n), c ≡ d (mod n)

ならば、

a+c ≡ b+d (mod n)
ac ≡ bd (mod n)

です。

例:

17 ≡ 2 (mod 5)
23 ≡ 3 (mod 5)
17・23 ≡ 2・3 ≡ 6 ≡ 1 (mod 5)

8. 逆元

mod n における a の逆元とは、

ax ≡ 1 (mod n)

を満たす x のことです。これを a^{-1} と書くことがあります。

逆元が存在する条件は次です。

a が mod n で逆元を持つ ⇔ gcd(a,n)=1

例: 3 の mod 7 における逆元。

3・5 = 15 ≡ 1 (mod 7)

したがって 3^{-1} ≡ 5 (mod 7) です。

9. 拡張Euclid法

逆元は、Bézout 等式から求められます。

例: 3^{-1} mod 7。

7 = 2・3 + 1
1 = 7 - 2・3

したがって

1 = 7・1 + 3・(-2)

です。mod 7 で見ると、

3・(-2) ≡ 1 (mod 7)

-2 ≡ 5 (mod 7) なので、逆元は 5 です。

10. 素数と Fermat の小定理

素数 p は、正の約数が 1 と p だけの2以上の整数です。

Fermatの小定理:

p が素数で、p ∤ a ならば a^(p-1) ≡ 1 (mod p)

例: p=7, a=3。

3^6 = 729 ≡ 1 (mod 7)

この定理は、公開鍵暗号の基礎に現れます。

11. 群

群は、1つの演算を持つ集合です。集合 G と演算 * が群であるとは、次を満たすことです。

  1. 閉性: a,b∈G なら a*b∈G。
  2. 結合律: (a*b)*c = a*(b*c)。
  3. 単位元: ある e∈G があり、e*a = a*e = a。
  4. 逆元: 各 a∈G に対し、a*b=b*a=e となる b∈G が存在する。

さらに a*b=b*a が常に成り立つなら、可換群です。

例:

整数全体 Z は、加算 + について可換群。
0 が単位元、-a が a の逆元。

12. mod n の乗法群

mod n において逆元を持つ剰余類全体は、乗法について群になります。

Z_n^* = { a mod n | gcd(a,n)=1 }

例: mod 8。

Z_8^* = {1,3,5,7}

各要素は mod 8 で乗法逆元を持ちます。

13. 巡回群と生成元

群 G のある要素 g のべき乗だけで G の全要素を生成できるとき、G は巡回群で、g を生成元と呼びます。

G = <g>

例: mod 7 の非零要素 {1,2,3,4,5,6} は乗法群です。3 のべき乗を見ると、

3^1 ≡ 3
3^2 ≡ 2
3^3 ≡ 6
3^4 ≡ 4
3^5 ≡ 5
3^6 ≡ 1        (mod 7)

すべての非零要素が出るので、3 は生成元です。

14. 離散対数問題

巡回群 G=<g> で、

h = g^x

が与えられたとき、x を求める問題を離散対数問題と呼びます。

通常の実数の対数とは違い、有限群の中での指数の逆問題です。大きな群では、特定の条件下でこれが難しいと考えられ、Diffie-Hellman や ElGamal の安全性に関係します。

15. 環と体

群より少し構造を増やしたものが環や体です。

環

加算と乗算を持ち、整数のように計算できる構造です。例として Z_n があります。

体

加算・減算・乗算・除算ができる構造です。ただし0で割ることはできません。

素数 p に対して、mod p の剰余類は体になります。

F_p = {0,1,...,p-1}

例: F_2 = {0,1}。情報理論や符号理論では、F_2 上の線形代数が重要です。

16. RSA の最小構造

RSAでは、大きな素数 p, q を使い、

n = pq

を作ります。公開鍵には n と指数 e が含まれ、秘密鍵には p, q や復号指数 d が関係します。

理論を読むために必要なのは、次です。

  • mod n で計算する。
  • 逆元を求める。
  • 素因数分解の困難性が関係する。
  • 指数法則が剰余環で使われる。

この章では安全性証明までは扱いません。暗号の章で式を追うための記法準備に留めます。

17. Diffie-Hellman の最小構造

Diffie-Hellman では、群 G と生成元 g を使います。

A = g^a
B = g^b
共通値 = g^(ab)

第三者は g, A, B を見ても、g^(ab) を計算しにくいという仮定に基づきます。ここで、指数計算、群、離散対数問題の記法が必要になります。

18. よくある誤り

誤り1: a/b mod n と書いて普通の割り算をする

mod n で割り算に相当する操作は、逆元を掛けることです。逆元が存在しない場合、割り算は定義できません。

誤り2: ab ≡ ac なら常に b ≡ c と考える

a が mod n で逆元を持つ場合だけ、両辺を a で消去できます。

誤り3: 群の演算を常に加算だと思う

群の演算は加算とは限りません。乗法、関数合成、楕円曲線上の演算などもあります。

誤り4: mod n での値を整数そのものと混同する

17 ≡ 2 (mod 5) ですが、整数として 17=2 ではありません。剰余類として同じ、という意味です。

19. 章末確認

次を説明できれば、この章の目的は達成です。

  1. a | b と a ≡ b (mod n) を定義できる。
  2. Euclidの互除法で gcd を計算できる。
  3. mod n における逆元の存在条件を言える。
  4. 群、単位元、逆元の意味を説明できる。
  5. 巡回群と生成元の意味を説明できる。
  6. 離散対数問題を式で説明できる。
  7. F_p と F_2 の意味を読める。

次に読む章

Edit this page on GitHub