[암호학] 3. 기초 대수학

[암호학] 3. 기초 대수학

집합 $G(\neq\emptyset)$위에 이항연산 $*$가 정의되어 있고, 즉 임의의 $a,\,b\in G$에 대해 $a*b\in G$이고, 또한 임의의 $a,\,b,\,c\in G$에 대해 다음의 공리를 만족하면, $\langle G,\,*\rangle$를 군(group)이라 하고, $G$는 연산 $*$에 대해 군을 이룬다고 한다.

(G1): $(a*b)*c=a*(b*c)$  

(G2): 적당한 원소 $e\in G$가 존재해서 모든 $a\in G$에 대해 다음이 성립한다. $$a*e=e*a=a$$ $e$를 $G$의 항등원(identity)이라고 한다.

(G3): 모든 $a\in G$에 대하여 $a'\in G$가 존재해서 다음이 성립한다. $$a*a'=a'*a=e$$ $a'$를 $a'$를 $a$의 역원(inverse)이라 하고 $a^{-1}$로 나타낸다. 

교환법칙이 성립하는 군을 아벨군(abelian group)이라고 한다. 

군 $\langle G,\,*\rangle$에서 $G$가 무한집합이면 무한군(infinite group), 유한집합이면 유한군(finite group)이라고 한다. $G$가 유한군일 때 $|G|$($G$의 원소의 개수)를 군 $G$의 위수(order)라고 한다. 

군에서 혼동의 여지가 없을 때 연산을 생략하고 여러번 연산하는 것을 다음과 같이 나타낸다. $$a^{n}=\begin{cases}aa\cdots a&\,(n>0)\\e&\,(n=0)\\(a^{m})^{-1}&\,(n=-m<0)\end{cases}$$ 군 $\langle G,\,*\rangle$에서 $G$의 부분집합 $H(\neq\emptyset)$가 $G$의 연산 $*$에 대해 군을 이루면, 즉 $\langle H,\,*\rangle$가 군이면, $H$를 $G$의 부분군(subgroup)이라 하고 $H\leq G$ 또는 $G\geq H$로 나타낸다. 

군 $G$의 부분집합 $H$에 대하여 다음은 서로 동치이다. 

(a) $H$는 $G$의 부분군이다. 

(b) $a,\,b\in H$이면 $ab\in H$이고 $a^{-1}\in H$이다. 

(c) $a,\,b\in H$이면 $ab^{-1}\in H$이다. 

군 $G$의 임의의 원소 $a\in G$에 대하여 $$\langle a\rangle=\{a^{i}\,|\,i\in\mathbb{Z}\}=\{\cdots,\,a^{-2},\,a^{-1},\,e,\,a,\,a^{2},\,\cdots\}$$ 일 때 $\langle a\rangle$는 군 $G$의 부분군이고, 이 부분군 $\langle a\rangle$를 $a$에 의해 생성된 순환부분군(cycle subgroup)이라고 한다. 

군 $G$의 적당한 원소 $a\in G$에 대해 $G=\langle a\rangle$이면, $G$를 순환군(cyclic group)이라 하고, $a$를 $G$의 생성원(generator)이라고 한다. $G$가 유한군일 때 $a\in G$에 대하여 $a^{r}=e$를 만족하는 최소의 정수 $r$을 $a$의 위수(order)라고 한다. 

군 $G$의 원소 $a$의 위수가 $r$일 때 다음이 성립한다. 

(a) 임의의 $n\in\mathbb{Z}$에 대하여 $a^{n}=e$이면 $r|n$이다.  

(b) $s,\,t\in\mathbb{Z}$에 대하여 $a^{s}=a^{t}$일 필요충분조건은 $s\equiv t\,(\text{mod}\,r)$이다. 

(c) 임의의 $n\in\mathbb{Z}$에 대하여 $a^{n}$의 위수는 $\displaystyle\frac{n}{\text{gcd}(n,\,r)}$이다. 

(d) $\text{gcd}(n,\,r)=1$일 필요충분조건은 $a^{n}$의 위수가 $r$이다.       

라그랑주 정리(Lagrange theorem) $G$가 유한군이면 다음이 성립한다. 

(a) $G$의 임의의 부분군 $H$에 대하여 $|H|$는 $|G|$의 약수이다.   

(b) 임의의 $a\in G$에 대하여 $|G|=n$일 때 $a^{n}=e$이고 따라서 $a$의 위수가 $r$이면 $r|n$이다. 

집합 $R$에 덧셈 $+$와 곱셈 $\cdot$가 다음의 공리를 만족하면, $\langle R,\,+,\,\cdot\rangle$을 환(ring)이라고 한다.

(R1): $\langle R,\,+\rangle$는 아벨군이다. 

(R2): 곱셈에 대해 결합법칙이 성립한다.

(R3): $a,\,b,\,c\in R$일 때 다음이 성립한다. $$\begin{align*}a\cdot(b+c)&=a\cdot b+a\cdot c\\(a+b)\cdot c&=a\cdot c+b\cdot c\end{align*}$$ 환 $R$에서의 덧셈에 대한 항등원은 0이다. 

환 $R$이 곱셈에 대한 항등원인 단위원(unity) 1을 가지면 $R$을 단위원을 갖는 환(ring with unity)이라고 하고, 곱셈에 대해 교환법칙이 성립하면 $R$을 가환환(commutative ring)이라고 한다. 또한 $R$이 단위원을 갖는 가환환이고, 덧셈항등원 0을 제외한 모든 원소가 곱셈에 대한 역원을 가지면, 이 환 $R$을 체(field)라고 한다. 이때 곱셈에 대한 역원을 단원(unit)이라고 한다.  

유리수 $\mathbb{Q}$, 실수 $\mathbb{R}$, 복소수 $\mathbb{C}$는 체이다. 

2 이상의 정수 $n$에 대해 $\mathbb{Z}_{n}=\{0,\,1,\,...,\,n-1\}$의 임의의 원소 $a,\,b$에 대해 $a+b$, $ab$를 다음과 같이 정의하자. $$\begin{align*}a+b=c\,(c\in\mathbb{Z}_{n})&\,\Leftrightarrow\,a+b\equiv c\,(\text{mod}\,n)\\ab=d\,(d\in\mathbb{Z}_{n})&\,\Leftrightarrow\,ab\equiv d\,(\text{mod}\,n)\end{align*}$$ 그러면 $\mathbb{Z}_{n}$은 단위원 1을 갖는 가환환이고, 이 환 $\mathbb{Z}_{n}$을 법 $n$에 대한 정수환이라고 한다.

가환환 $\mathbb{Z}_{n}=\{0,\,1,\,...,\,n-1\}$에서 $a\in\mathbb{Z}_{n}$가 단원, 즉 곱셈에 대한 역원을 가질 필요충분조건은 $\text{gcd}(a,\,n)=1$이다. 

위 정리로부터 소수 $p$에 대해 $\mathbb{Z}_{p}$의 0이 아닌 모든 원소들은 단원이고 따라서 $\mathbb{Z}_{p}$는 체이다. 

단위원을 갖는 가환환 $R$의 $mn$개의 원소 $a_{ij}\,(1\leq i\leq m,\,1\leq j\leq n)$를 다음과 같이 직사각형 모양으로 나열한 것을 $R$위의 $m\times n$행렬(matrix)이라고 한다. $$A=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\a_{m1}&a_{m2}&\cdots&a_{mn}\end{pmatrix}$$ 위의 행렬을 간단히 $A=(a_{ij})_{m\times n}$로 나타낸다. 모든 성분이 0인 $m\times n$행렬을 $m\times n$영행렬이라고 하고 이 행렬을 $O_{m\times n}$ 또는 간단히 $O$로 나타낸다. 

가환환 $R$위의 $m\times n$행렬 전체의 집합을 $M_{m\times n}(R)$로 나타내고 이 집합 위에서 덧셈과 뺄셈, 스칼라곱은 다음과 같이 정의된다. $$\begin{align*}(a_{ij})_{m\times n}\pm(b_{ij})_{m\times n}&=(a_{ij}\pm b_{ij})_{m\times n}\\ \alpha(a_{ij})_{m\times n}&=(\alpha a_{ij})_{m\times n}\end{align*}$$ 가환환 $R$ 위의 $m\times n$행렬 $A=(a_{ij})_{m\times n}$과 $n\times r$행렬 $B=(b_{ij})_{n\times r}$에 대해 곱 $AB$는 다음과 같이 정의되는 $m\times r$행렬이다. $$AB=(c_{ij})_{m\times r},\,\left(c_{ij}=\sum_{k=1}^{n}{a_{ik}b_{kj}}=a_{i1}b_{1j}+\cdots+a_{in}b_{bj}\right)$$ 가환환 $R$ 위의 $m\times n$행렬 $A=(ㅁ_{ij})_{m\times n}$에 대해 각 $(i,\,j)$성분이 $a_{ji}$인 $n\times m$행렬을 $A$의 전치(transpose)행렬이라 하고 이것을 $A^{T}$로 나타낸다. 즉 $$A^{T}=\begin{pmatrix}a_{11}&a_{21}&\cdots&a_{n1}\\a_{12}&a_{22}&\cdots&a_{n2}\\ \vdots&\vdots&\ddots&\vdots\\a_{1n}&a_{2n}&\cdots&a_{mn}\end{pmatrix}$$ 이때 두 $m\times n$행렬 $A,\,B$에 대하여 $$(A^{T})^{T}=A,\,(A+B)^{T}=A^{T}+B^{T}$$ 이고, 또한 $m\times n$행렬 $A$와 $n\times r$행렬 $B$에 대해 $(AB)^{T}=B^{T}A^{T}$이다. 

가환환 $R$위의 $n\times n$행렬을 $n$차 정사각행렬(square matrix)이라고 하고, 대각선의 모든 성분이 1이고 그 이외의 성분이 모두 0인 정사각행렬을 단위행렬이라고 하고 $I_{n}$으로 나타낸다. 

정사각행렬은 행렬합과 행렬곱에 대해 환의 공리를 만족하므로 가환환 $R$위의 $n$차 정사각행렬들의 집합을 $M_{n}(R)$이라고 하면 $M_{n}(R)$은 환이다. 

가환환 $R$위의 정사각행렬 $A(\neq O)\in M_{n}(R)$에 대해 $A^{-1}\in M_{n}(R)$가 존재해서 $$A^{-1}A=AA^{-1}=I_{n}$$ 이면, $A$는 정칙행렬(nonsingular matrix), $A^{-1}$를 $A$의 역행렬(inverse matrix)이라고 한다. 

$M_{n}(R)$의 정칙행렬 전체의 집합을 $GL(n,\,R)$이라고 하면, $GL(n,\,R)$은 곱셈에 대해 군을 이루고, 이것을 $n$차 일반선형군(general linear group)이라고 한다. 

$A=(a_{ij})_{n\times n}$에 대해 $A$의 행렬식(determinant)을 정의할 수 있고, $2\times 2$행렬에 대해서 다음과 같고, $$\det\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}=a_{11}a_{22}-a_{12}a_{21}$$ 행렬식은 다음의 성질들을 갖는다. $$\det I_{n}=1,\,\det AB=(\det A)(\det B)$$ 행렬 $A=(a_{ij})_{n\times n}$의 원소 $a_{ij}$에 대해 $A$의 $i$행과 $j$열을 제거한 행렬의 행렬식을 $a_{ij}$에서의 소행렬식(minor)이라고 하고, $M_{ij}$로 나타낸다. 또한 $A_{ij}=(-1)^{i+j}M_{ij}$를 $a_{ij}$의 여인수(cofactor)라 하고, 행렬 $$\text{adj}A=(A_{ij})_{n\times n}^{T}=\det\begin{pmatrix}A_{11}&A_{12}&\cdots&A_{n1}\\A_{12}&A_{22}&\cdots&A_{n2}\\ \vdots&\vdots&\ddots&\vdots\\A_{1n}&A_{2n}&\cdots&A_{nn}\end{pmatrix}$$ 를 $A$의 수반(adjoint)행렬이라고 한다. 이때 다음이 성립한다. $$A(\text{adj}A)=(\text{adj}A)A=(\det A)I=\begin{pmatrix}\det A&0&\cdots&0\\0&\det A&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\0&0&\cdots&\det A\end{pmatrix}$$ 위의 사실로부터 $A$가 정칙행렬이기 위한 필요충분조건은 $(\text{det}A)^{-1}$가 존재하는 것이고, 이때 $A^{-1}=(\det A)^{-1}\text{adj}A$이다. 

$A\in M_{2}(R)$이 다음과 같으면 $$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$$ $\det A=ad-bc$이므로 $ad-bc\neq0$일 때 역행렬을 갖고, 그 역행렬은 다음과 같다. $$A^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$$ 참고자료:

암호학과 부호이론, 박승안, 경문사

A First Course in Abstract Algebra 7th edition, Fraleigh, Addison-Wesley