代数，情報・暗号理論

$a$ と $b$ が互いに素なとき $ax\equiv 1\pmod{b}$ なる $x$ が $1\leq x\leq b-1$ の間ではただ一つ存在する。

$a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_n$ を正の数とするとき， $$\sum a_k\log\dfrac{a_k}{b_k} \geqq \left(\sum a_k \right) \log\dfrac{\sum a_k}{\sum b_k}$$

確率 $p$ で起こる事象を観測したときに得られる（自己）情報量を $-\log_2 p$ bitと定義する。

$n$ 個の変数の全てのペアの差の積： $$\Delta (x_1 , \cdots , x_{n})= \prod_{1 \leq i < j \leq n} (x_j -x_i)$$

を差積（最簡交代式，基本交代式）と言う。

相互情報量は，確率変数の間の「依存度」を表す指標。

$A,B$ を環とする。$\phi : A \rightarrow B$ が次の条件を満たすとき，$\phi$ を準同型という。

1. 任意の $x,y \in A$ に対して次の式が成り立つ。 $$\phi (x+y) = \phi (x) + \phi (y)\\ \phi (xy) = \phi (x) \phi (y)$$

2. $\phi (1_A) = 1_B$ である。

集合 $A,B$ がある。任意の $a \in A$ に対して，$B$ の要素を1つ返すような対応 $f$ を $A$ から $B$ への 写像 という。またこのとき $$f : A \rightarrow B$$ と書くことがある。

三大作図問題とは

• 円積問題
• 立方体倍積問題
• 角の3等分問題

の3つのことである。

群 $(G,\cdot)$ の部分集合 $H$ が $G$ の演算 $\cdot$ で群となるとき，$H$ を 部分群 という。

群 $G$ から群 $H$ への写像 $\phi$ について，任意の $g_1 , g_2 \in G$ に対して $$\phi (g_1 g_2) = \phi (g_1) \phi (g_2)$$ であるとき，$\phi$ を準同型写像と言う。

• 群 $G$ の部分群 $N$ が正規部分群であるとは，
  任意の $g \in G, n \in N$ に対して $g^{-1} n g \in N$ である
  ことを表す。
• 正規部分群は「その剰余集合が群になる（剰余群が定まる）」ので嬉しい

• 群 $G$ の位数とは，$G$ の元の個数のことである。$|G|$ と書くことが多い。

• 元 $x\in G$ の位数とは，$x^n = 1_G$ となる最小の $n$ のことである。ただし $1_G$ は $G$ の単位元とする。

群 $G$ の部分群 $H$ の指数が有限であるとする。

このとき $H$ は指数有限の正規部分群を含む。

群 $G$ がリー群であるとは，次の2条件を満たすことをいう。

1. $G$ は多様体である。
2. $G$ の演算（積および逆元を取る操作）は多様体の $C^{\infty}$ 級写像になる。

有限群 $G$ について，その位数を $|G|=p^km$ とする（ただし $p$ は素数で，$m$ は $p$ の倍数でないとする）。

このとき，$G$ の部分群で位数が $p^k$ であるものが存在する。

環 $A$ の空でない部分集合 $I$ が次の条件を満たすとき，$I$ を $A$ のイデアルという。

1. 任意の $x,y \in I$ に対して，$x+y \in I$ （すなわち，$I$ は加法に関して $A$ の部分群）
2. 任意の $a \in A, x \in I$ に対して，$ax \in I$

環 $A$ が 整域 であるとは，次の条件を満たすことをいう。

• $x,y \in A$ が $xy = 0_A$ を満たすのならば，$x = 0_A$ もしくは $y = 0_A$ である。

$n$ 次の置換全体の集合は，置換の積に関して群を成す。これを対称群（置換群）といい，$\mathfrak{S}_n$ や $S_n$（$\mathfrak{S}$ は $S$ のドイツ文字）などと書く