chapter 4 대칭 키 암호 수학: 대수 구조 - 1절 대수 구조

1. 대수 구조의 개념

 한 집합과 그 집합에 포함된 원소들에 적용되는 연산들을 통틀어 대수 구조(algebraic structure)라고 한다. 일반적인 대수구조로는 군, 환, 체가 있다.

 

2. 군

 군(groups, G)은 네 개의 성질을 만족하는 이항연산 "●"이 정의된 원소들의 집합이다. G = <{...}, ●>로 표기한다. 특히, 군 중에서 교환 법칙을 만족하는 집합을 가환 군(commutative group) 또는 아벨 군(abelian group)이라고 한다.

닫힘(closure)
 만약 a와 b가 G의 원소라면, c = a ● b 또한 G의 원소이다.

결합 법칙(associativity)
 만약 a, b, c가 G의 원소라면, (a ● b) ● c = a ● (b ● c)를 만족한다.

항등원의 존재성(existence of identity)
 G의 임의의 원소 a에 대하여, e ● a = a ● e = a를 만족하는 항등원(identity element) e가 존재한다.

역원의 존재성(existence of inverse)
 G의 임의의 원소 a에 대하여, a ● a' = a' ● a = e를 만족하는 a의 역원(inverse) a'이 존재한다.

교환 법칙(commutativity)
 G의 임의의 두 원소 a, b에 대하여, a ● b = b ● a를 만족한다.

1. 응용
 하나의 군에는 한 개의 연산만이 정의되지만, 그 연산에 대한 성질들은 그 연산과 역함수 관계에 있는연산의 사용을 허용한다.

2. 유한 군
 유한 군(finite group)은 유한개의 원소를 갖고 있는 군이다. 반대 개념으로 무한 군(infinite group)이 있다.

3. 군의 위수
 군의 위수(order) |G|는 군에 있는 원소의 개수이다.

4. 부분군
 부분군(subgroup)은 군의 부분집합 중 그 자신이 군이 되는 부분집합이다. 

5. 순환 부분군
  순환 부분군(cyclic subgroup)은 어떤 원소의 멱승(power)를 사용하여 생성된 부분군이다. 멱승이란 원소애 군의 연산을 반복적으로 적용한 것을 의미한다.

6. 순환 군
 순환 군(cyclic groups)은 그 자신이 하나의 순환 부분군인 군이다. 순환 군을 생성하는 원소를 생성원(generator)라고 한다.

7. 라그랑지 정리
 라그랑지 정리(Lagrange's theorem)는 부분군의 위수가 군의 위수를 나눈다는 정리다.

8. 원소의 위수
 a^n = e를 만족하는 가장 작은 정수 n을 원소 a의 위수(order)라고 하며 ord(a)라고 한다.

 

3. 환

 환(ring)은 두 개의 연산이 정의된 대수 구조이다. G = <{...}, ●, ■>로 표기한다. 첫 번째 연산은 아벨 군에 대해 요구되는 다섯 가지 성질을 만족해야 한다. 두 번째 연산은 닫힘과 결합 법칙만 만족하면 된다. 또한 두 번째 연산은 첫 번째 연산 위에 분배법칙(distributivity)를 만족해야 한다. 특히, 두 번째 연산이 교환법칙을 만족하면 가환 환(commutative ring)이라고 한다.

 

4. 체

체(field)는 두 번쨰 연산이 특정한 성질을 만족하는 가환 환이다. 두 번째 연산이 첫 번째 연산의 항등원이 역원을 갖지 않는다는 것을 제외하고 군의 모든 다섯가지 성질을 만족해야 한다.

 

1. 응용
 체는 일반적으로 수학에서 사용되는 덧셈/뺄셈과 곱셈/나눗셈 연산의 두 쌍들을 사용할 수 있는 구조이다. 하지만 0으로 나누는 것을 제외한다.

2. 유한 체
 유한 체(finite field)는 유한 개의 원소를 갖는 체이다. 갈로아(Galois)는 유한 개의 원소를 갖는 체에 대하여 원소의 개수가 p^n임을 보였다. 여기서 p는 소수이고 n은 양의 정수이다. 따라서 유한 체는 갈로아 체(Galois field)라고 불리며  GF(p^n)으로 표현한다.

3. GF(p) 체
 n = 1일 때 갈로아 체는 GF(p)이다.

4. GF(p^n) 체
 GF(p^n) 체는 암호학에서 매우 중요한 체이다. 다음 절에서 자세히 알아본다.