Memorandum

代数学

●二項演算

集合 \(A\) に対して、写像 \(f : A \times A \rightarrow A\) を \(A\) 上の「二項演算」といいます。たとえば、実数の加減乗除は、2 つの実数から新しい実数を生成しているで、実数上の二項演算になります。二項演算は \(a \cdot b \ (a, b \in A)\) のように記号 (\(\cdot, +\) など) を使って表すのがふつうです。

●二項演算の三法則

集合 \(A\) 上に演算 \(\cdot\) が定まっているとします。このとき、任意の \(a, b, c \in A\) に対して、以下の法則を定義します。

• \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) が成り立つことを「結合法則」を満たすという
• \(a \cdot b = b \cdot a\) が成り立つことを「交換法則」を満たすという
• 集合 \(A\) 上に 2 つの演算 \(\cdot, \circ\) が定まっているとする。以下の式が成り立つことを「分配法則」を満たすという
• \(a \cdot (b \circ c) = (a \cdot b) \circ (a \cdot c)\)
• \((a \circ b) \cdot c = (a \cdot c) \circ (b \cdot c)\)

実数の積と和は上記三法則を満たします。

なお、交換法則が成り立たない数を考えることもできます。交換法則が成り立つことを「可換」といい、成り立たないっことを「非可換」といいます。

●群

集合 \(G\) 上に演算 \(\cdot\) が定まっているとします。次の３条件を満たすとき、集合と演算の組 \((G, \ \cdot)\) を「群 (group)」といいます。

1. 結合法則を満たすこと
2. ある \(e \in G\) が存在し、任意の \(a \in G\) に対して、\(a \cdot e = e \cdot a = a\) を満たすこと
3. 任意の \(a \in G\) に対して、\(a \cdot b = b \cdot a = e\) を満たす \(b \in G\) が存在すること

2 の \(e\) を「単位元」といいます。3 の \(b\) を \(a\) の「逆元」といい、\(a^{-1}\) と表記します。これに加えて「交換法則」が成り立つ場合、「可換群」とか「アーベル群」といいます。

たとえば、整数と通常の加法の組 \((\mathbb{Z}, +)\) を考えてみましょう。

• 整数の加法は結合法則を満たしている
• 単位元 (0) が存在する
• \(a\) の逆元 \((-a)\) が存在する

以上のことから \((\mathbb{Z}, +)\) は群であることがわかります。また、整数の加法は交換法則を満たすので可換群になります。これに対し、整数と通常の乗法の組 \((\mathbb{Z}, \times)\) は群になりません。

• 整数の乗法は結合法則を満たしている
• 単位元 (1) が存在する
• \(a\) の逆元は \(\pm 1\) しか存在しない
• \(a = 0\) の場合、\(0 \cdot b = b \cdot 0 = 0\) になる
• \(a \ne 0\) の場合、\(a \cdot b = b \cdot a = 1\) を満たすのは \(b = \pm 1\), または \(b = \frac{1}{a}\) (有理数になる)

逆元は存在しないので、\((\mathbb{Z}, \times)\) は群ではありません。

●環

集合 \(R\) 上に 2 つの演算 \(+, \cdot\) が定まっているとします。次の 4 つの条件を満たすとき、集合と演算の組 \((R, \ +, \ \cdot)\) を「環 (ring)」といいます。

1. \((R, +)\) が可換群であること
2. ある \(e \in R\) が存在し、任意の \(r \in R\) に対して、\(r \cdot e = e \cdot r = r\) を満たすこと
3. 演算 \(\cdot\) に関して結合法則が成り立つこと
4. 演算 \(+, \ \cdot\) に関して分配法則が成り立つこと

このとき、\(+\) を「加法」といい、\(\cdot\) を「乗法」といいます。加えて、演算 \(\cdot\) に交換法則が成り立つとき、環 \((R, \ +, \ \cdot)\) は「可換環」であるといいます。

条件 1 から環の加法には単位元が存在します。これを「加法の単位元」と「零元」といい、0 で表します。条件 2 を「乗法の単位元」といい、1 で表します。環の場合、加法の逆元は存在しますが、乗法の逆元は無くてもかまいません。

たとえば、整数と通常の加法と乗法の組 \((\mathbb{Z}, +, \cdot)\) を考えてみましょう。

• 整数の加法は可換群である
• 整数の乗法は単位元 (1) が存在する
• 整数の乗法は結合法則が成り立つ
• 整数の加法と乗法は分配法則が成り立つ

以上より、\((\mathbb{Z}, +, \cdot)\) は環であることがわかります。また、整数の乗法は交換法則が成り立つので、可換環になります。

成分が実数の n 次正方行列の集合と行列の和と積の組 \((Mat_n(\mathbb{R}),\ + , \cdot)\) は環ですが、非可環になります。

• \(Mat_n(\mathbb{R})\) の加法は可換群である
• \(Mat_n(\mathbb{R})\) の乗法は単位元 (単位行列 \(E\)) が存在する
• \(Mat_n(\mathbb{R})\) の乗法は結合法則が成り立つ
• \(Mat_n(\mathbb{R})\) の加法と乗法は分配法則が成り立つ
• \(Mat_n(\mathbb{R})\) の乗法は交換法則が成り立たない (\(AB \ne BA\))

●体

集合 \(F\) 上に 2 つの演算 \(+, \cdot\) が定まっているとします。次の条件を満たすとき、集合と演算の組 \((F, \ +, \ \cdot)\) を「体 (field)」といいます。

1. \(F\) は可換環であること
2. 0 を除くすべての元 (\(a \in F\)) で、乗法逆元 \(a^{-1}\) が存在すること

有理数、実数、複素数は体になります。加法と乗法の逆元が存在するので、体では四則演算 (加減乗除) を行うことができます。

●有限体

数学の世界では、加減乗除ができる数の集合のことを「体 (field)」といいました。特に、数が \(n\) 個しかないものを「有限体 (finite field)」または「ガロア体 (Galois field)」といいます。ここでは \(GF(n)\) と表記することにします。\(n\) が素数のとき、その剰余の集合 \(\{0, 1, \ldots, n - 1\}\) は有限体になります。簡単な例として \(GF(2)\) と \(GF(3)\) の加法と乗法を示します。

mod n の世界では、加法と乗法は簡単に計算できます。加算または乗算したあと mod n を計算するだけです。減算は負数 (加法の逆元) を、徐算は逆数 (乗法の逆元) を考えます。\(x + y = 0\) を満たす \(y\) が \(x\) の負数になるので、\(y = n - x\) であることがわかります。0 以外の数の逆数が存在すれば徐算が可能になります。乗法の表を見れば、\(GF(2)\) は \(1 \times 1 = 1\), \(GF(3)\) は \(1 \times 1 = 1, 2 \times 2 = 1\) となるので、徐算が成り立つことがわかります。

n が素数ではない場合、逆数が存在しない数があります。たとえば、mod 4 の加法と乗法は次のようになります。

mod 4 の場合、加算、乗算、減算は成り立ちますが、徐算で 2 の逆数が存在しないことが乗法の表からわかります。つまり、有限体にはならないわけです。

●拡大体

\(4\) の剰余 \(\{0, 1, 2, 3\}\) は \(GF(4)\) になりませんが、\(GF(2)\) に新しい数を付け加えることで、数が \(4\) つある有限体を作ることができます。新しい数を付加して体を拡張することを「体の拡大」といい、拡大された体を「拡大体」といいます。

たとえば、実数の世界では代数方程式 \(x^{2} + 1 = 0\) に解はありませんが、虚数 \(i\) を導入した複素数の世界では解くことができますね。複素数の世界は実数の拡大体になるわけです。

\(GF(2)\) を拡大する場合、\(GF(2)\) 上の代数方程式を考えます。2 次方程式を列挙すると次のようになります。

1. \(x^{2} = 0\)
2. \(x^{2} + 1 = 0\)
3. \(x^{2} + x = 0\)
4. \(x^{2} + x + 1 = 0\)

この中で解を持たないのは式 4 です。『\(x\) の関数 \(f(x)\) において、\(f(a) = 0\) ならば \((x - a)\) で割り切れる』という性質を「因数定理」といいます。式 1, 2, 3 を因数分解すると次のようになります。

1. \(x^{2} = (x + 0)(x + 0)\)
2. \(x^{2} + 1 = (x + 1)(x + 1)\)
3. \(x^{2} + x = (x + 0)(x + 1)\)

式 4 は \(GF(2)\) で因数分解することはできません。これを「既約多項式」といいます。既約多項式は多項式の素数みたいなもので、1 次多項式 \(x, \ x + 1\) で割り切れることはありません。この式の解の一つを \(a\) としましょう。\(a^{2} + a + 1 = 0\) が成り立つので、\(a^{2} = a + 1\) であることがわかります。次に、\(a\) の累乗を計算します。

\(a, a + 1, 1\) が順番に現れています。これを多項式で表すと \(1, x, x + 1\) になり、1 次多項式がすべて現れていることがわかります。このように、累乗を計算すると n 次未満の多項式がすべて現れる既約多項式のことを「原始多項式」といいます。

これに 0 を加えた 4 つの要素 \(\{0, 1, x, x + 1\}\) を数として加法と乗法を考えてみましょう。基本的には式を計算して、それを既約多項式 \(x^{2} + x + 1\) で割った剰余が値になります。下図を見てください。

加法の場合は特に簡単で、係数ごとに加算して mod 2 をとる、つまり係数ごとの排他的論理和になります。乗算の場合は累乗の形式に変換して計算すると簡単です。つまり、\(a^{m} * a^{n} = a^{n+m} = a^{(n+m) \ \mathrm{mod} \ 3}\) になります。\(a^{2} = a + 1\) の関係を使って式を簡約してもかまいません。

減法の場合、加法表より負数が自分自身であることがわかるので、加法と同様に係数ごとの排他的論理和になります。徐算の場合、乗法表より \(1, x, x + 1\) の逆数がすべて存在するので、徐算が成り立つことがわかります。つまり、\(\{0, 1, x, x + 1\}\) は有限体になるわけです。多項式の係数をビットで表すと、加法と乗法は次のようになります。

\(p\) を素数とし、\(n\) を自然数とすると、要素数が \(p^{n}\) の有限体は必ず存在することが知られています。これを \(GF(p^{n})\) と表記します。\(GF(2^{n})\) はコンピュータとの相性が良いので、エラー検出、乱数の生成、暗号など多くの分野で応用されています。

ご参考までに、\(GF(2^{3})\) と \(GF(3^{2})\) の加法表と乗法表を示します。

●合同式の徐算

拡張ユークリッドの互除法は、合同式の徐算で逆数を求めるときにも役に立ちます。\(a \times b \equiv 1 \pmod n\) において a の逆数 b を求める場合、\(a \times x + n \times y = 1\) を求めます。ここで、\(\gcd(a, n) = 1\) が条件になることに注意してください。両辺に mod n を施すと \(n \times y\) は 0 になるので、\(a \times x \equiv 1 \pmod n\) が成り立ちます。つまり、x が a の逆数になるわけです。簡単な例を示しましょう。

>>> import sympy as sy
>>> for a in range(1, 11):
...     print(sy.gcdex(a, 11))
...
(1, 0, 1)
(-5, 1, 1)
(4, -1, 1)
(3, -1, 1)
(-2, 1, 1)
(2, -1, 1)
(-3, 2, 1)
(-4, 3, 1)
(5, -4, 1)
(-1, 1, 1)

\(n\) が素数の場合、\(n\) とその剰余は互いに素になります。合同式で \(x\) の負数 \(-x\) は \((n - x)\) になるので、mod 11 における 1 から 10 までの逆数は次のようになります。

  x   1/x
 -------------------------
  0   ---
  1    1     1 mod 11 = 1
  2    6    12 mod 11 = 1
  3    4    12 mod 11 = 1
  4    3    12 mod 11 = 1
  5    9    45 mod 11 = 1
  6    2    12 mod 11 = 1
  7    8    56 mod 11 = 1
  8    7    56 mod 11 = 1
  9    5    45 mod 11 = 1
 10   10   100 mod 11 = 1

\(n\) が素数でない場合、\(n\) とその剰余は互いに素になるとは限りません。次の例を見てください。

>>> for x in range(1, 8): print(sy.gcdex(x, 8))
...
(1, 0, 1)
(1, 0, 2)
(3, -1, 1)
(1, 0, 4)
(-3, 2, 1)
(-1, 1, 2)
(-1, 1, 1)

2, 4, 6 と 8 の最大公約数は 1 にならないので、その逆数を求めることはできません。つまり、mod 8 の世界では 2, 4, 6 で割り算することはできないわけです。

また、フェルマーの小定理から逆数を求めることもできます。

\(a \times a^{n-2} \equiv 1 \pmod n\) が成り立つので、逆数は \(a^{n-2}\) になります。それでは実際に試してみましょう。

>>> for x in range(1, 11): print(x, x**9, pow(x, 9, 11))
...
1 1 1
2 512 6
3 19683 4
4 262144 3
5 1953125 9
6 10077696 2
7 40353607 8
8 134217728 7
9 387420489 5
10 1000000000 10

Python の関数 pow(x, y) は \(x^y\) を計算しますが、第 3 引数に n を指定すると、べき剰余を求めることができます。累乗を計算してから mod をとるよりも高速に計算することができます。結果は拡張ユークリッドの互除法と同じになりましたね。

●参考 URL

1. 奥村晴彦,『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
2. ガロア体と拡大体, (kei@sodan さん)
3. 有限体, (塩田研一さん)
4. 拡張ユークリッド互除法, (tbasic.org さん)
5. 中国剰余定理の証明と例題（二元の場合）, (マスオさん)
6. 中国剰余定理と法が互いに素でない場合への拡張, (マスオさん)
7. ユークリッドの互除法 - Wikipedia
8. ベズーの等式 - Wikipedia
9. 中国の剰余定理 - Wikipedia