[암호학] 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