#8. 기초 대수학

Group (군) 정의

공개키 암호 알고리즘이 정의되는 수학적 구조

RSA 암호, ELGamal 암호, DSA 전자서명

타원곡선

 

 

Group의 정의

공집합이 아닌 집합 G와 G의 원소에 대해 다음을 만족하는 연산 ⊗가 정의 되면 (G, ⊗)를 Group이라고 부른다.

[결합법칙] 연산 ⊗에 대해 결합 법칙이 성립한다.

[항등원] G의 모든 원소 a에 대해 연산 ⊗에 대한 항등원 e∊G가 존재한다.

[역원] G의 각 원소 a에 대해 연산 ⊗에 대한 역원d이 존재한다.

 

 

Abelian group

가환군 또는 Commutative group

Group (G, ⊗) 에서 연산 ⊗에 대해 교환법칙이 성립하는 경우를 말함

-> 행렬같은건 안됨

 

Group order (위수)

Group G의 원소의 개수

|G|로 표기

 

 

Group 원소의 order

Group G의 원소 g의 위수 <=> g^n = 1이 되는최소 자연수

|g|로 표기

 

 

Cyclic Goup

Group (G, ⊗)의 모든 원소가 하나의 원소 g의 거듭제곱 (지수)로 표현되는 Group

생성 원소 g를 generator라고 부름

(표기) G = <g> = { 1, g, g^2, ... }

 

소수 p에 대해서 Zp*는 항상 cyclic group

 

 

Subgroup (부분군)

[정의] Group (G, ⊗)의 공집합이 아닌 부분집합 H⊂G

(H, ⊗)도 group이 되면 subgroup이라고 정의

표기: H≤G or H<G

 

 

Subgroup 성질

라그랑즈(Lagrange) 정리

Group G의 위수가 유한한 수 n이라고 하면, 모든 G의 subgroup H의 위수는 n의 약수이다.

즉, |H| | |G|

라그랑즈 정리의 역은 일반적으로는 성립하지 않는다.

아래에서는 유한한 위수 l을 가지는 Group Group G를 고려

임의의 g∊G에 대해 <g>는 G의 subgroup

H ≤G 이면 모든 h∊H에 대해 h^|G| = 1

 

 

Cyclic Group의 Subgroup

G=<g>, |g| = n에 대해 아래가 성립

Cyclic group G 의 subgroup H도 cyclic group

Cyclic group에서는 라그랑즈 정리의 역이 성립함.

g^m∊G의 위수 = n/gcd(n,m)

gcd(n,m)=1 -> G = <g> = <g^m>

 

 

 

 

Ring

Ring(환)

공집합이 아닌 집합 R와 R의 원소에 대해 다음을 만족하는 두 개의 +와 x이 정의되면 (R, +, x)를 Ring이라고 부른다.

1. [+에 대한 결합법칙]

2. [+에 대한 교환법칙]

3. [+에 대한 항등원]

4. [+에 대한 역원]

5. [×에 대한 결합법칙]

6. [분배법칙]

 

1, 2, 3, 4에 따라 (R, +)은 Abelian group

Ring은 Abelian group에서 5, 6을 만족하는 연산이 하나 더 추가된다.

 

 

 

 

 

Finite Field (유한체)

Field (체)

Ring (F, +, x)가 아래를 만족하면 field라고 정의한다.

1. [×에 대한 교환법칙]

2. [×에 대한 항등원]

3. [×에 대한 역원]

 

Finite field (유한체)

F가 field이고, F의 원소의 개수가 유한한 경우

Field는 연인자 (zero divisor)가 없다.

영인자: a와 b 모두 0이 아니지만 a x b = 0이 되는 경우