대수적 구조

<일반적인 대수적 구조>
- Common algebraic structures
  1. Groups
  2. Rings
  3. Fields



<군(Group)>
- 군(Group, G)은 네 개의 성질(혹은 공리)을 만족하는 이항연산이 정의된 원소들의 집합이다
- 가환군(Commutative group)혹은 아벨군(Abelian group)은 군에 대한 네 개의 성질에 교환법칙을 추가로 만족하는 집합니다
  - 닫힘(Closure)
  - 결합법칙(Associativity)
  - 교환법칙(Commutativity)
  - 항등원의 존재(Existence of identitiy)
  - 역원의 존재(Existence of inverse)



<군(Group)의 응용(Application)>
- 하나의 군에는 한 개의 연산만이 정의되지만, 그 연산에 대한 성질들은 그 연산과 역함수 관계에 있는 연산의 사용을 허용한다
- ex) 정의된 연산이 덧셈이라면 뺄셈은 덧셈의 역함수 관계를 가지기 때문에 군은 덧셈과 뺄셈 모두를 사용한다
       이것은 또한 곱셈과 나눗셈에 대해서도 적용된다

- 덧셈 연산이 정의된 잉여류(Residue Integers)의 집합  
  G=<Zn, +>은 가환군(Commutative group - 교환법칙)이다 
  이 군은 새로운 원소를 추가하지 않고 덧셈과 뺄셈 모두 사용할 수 있다

결과 -> 1. 집합은 연산에 대해서 닫혀있다. 왜냐하면 Zn의 두 원소에 대한 합은 Zn에 있는 다른 원소이기 때문이다
           2. 결합 법칙을 만족한다 Zn의 세 원소 a,b,c에 대하여, (a+b)+c = a+(b+c)
           3. 교환 법칙을 만족한다. Zn의 두 원소 a,b에 대하여, a+b = b+a
           4. 항등원은 0. Zn의 원소 a에 대하여, a+0 = 0+a=a
           5. 모든 원소는 덧셈에 대한 역원을 갖는다. 어떤 원소에 대한 역원은 그 원소의 보수(Complement)Zn의 원소 a에 대하여, a의 역원은
              n-a(Zn의 n-a)덧셈에 대한 역원은 집합에서 뺄셈을 사용할 수 있게 해준다

- 곱셈 연산이 정의된 집합 Zn*(G=<Zn*,x>)는 가환군이다
  이 군은 새로운 원소를 추가하지 않고 곱셈과 나눗셈 모두 사용할 수 있다
  이 군이 처음 세 가지 성질을 만족하는 것을 쉽게 보일 수 있다
  이 집합에 대한 항등원은 1이다

- 군에서, 집합의 원소들이 숫자나 어떤 물체일 필요가 없다
  그것은 규칙이나 사상(Mapping), 함수(Function)가 될 수도 있고 혹은 어떤 작용(Action)도 될 수 있다


<치환군>
- 치환군(Permutation group), 이 집합은 모든 치환을 모아 놓은 집합이며 이 집합에 정의된 연산은 두 치환에 대한 합성이다
- 합성 연산이 정의된 치환들의 집합은 군임을 보인다
  이는 하나의 치환을 수행한 후에 다른 치환을 수행하는 방법은 암호의 안전성을 강화시키지 못하는 것을 의미한다
  왜햐하면 군의 닫혀 있는 성질을 이용해서 항상 같은 결과값을 출력하는 다른 치환을 찾아낼 수 있기 때문이다



<유한군(Finite Group)>
- 유한개의 원소를 가지고 있는 군(Group)


<군의 위수(Order of a Group)>
- 군(Group)에 있는 우너소의 개수


<부분군(Subgroup)>
- 군 G의 원소에 대한 부분집합 H가 G에서의 연산에 대하여
  그 자신이 군이 될 때, 부분집합H는 군G에 대한 부분군(Subgroup)이라고 한다
- G=<S,*>가 군이고 T는 S에 포함되어질 때(T는 공집합이 아니다)
  H=<T,*>같은 연산 *에 대하여 군이 된다면 H는 G의 부분군


<순환 부분군(Cyclic Subgroup)>
- 만약 군의 부분군이 어떤 원소 멱승(power)을 사용하여 생성된다면 이 부분군을 순환 부분군(Cyclic Subgroup)이라고 한다
- 여기서 멱승은 원소에 군의 연산을 반복적으로 적용한 것을 의미한다
  A^n -> a*a*...*a (n times)
- 순환군(Cycle Group)은 그 자신이 하나의 부분군인 군이다
  {e, g, g^2, ... , g^(n-1)}, where g^n = e (e는 항등원, g는 generator)



<라그랑지 정리(Largrange's Theorem)>
- 라그랑지 정리(Largrange's Theorem)는 군의 위수와 부분군의 위수와 관련이 있다
- G가 군이고 H가 G의 부분군일 떄, G와 H의 위수를 각각 |G|, |H|라고 하면, 이 정리에 의해 |H|는 |G|를 이룬다
- |H| | |G|



<원소의 위수(Order of an Element)>
- 원소의 위수는 "그 원소가 생성하는 순환군의 위소"로 정의할 수도 있다
- 원소 a의 위수는 ord(a)로 표시한다



<환(Ring)>
- 환은 두 개의 연산을 가지는 대수족 구조이다
- 덧셈과 곱셈의 연산이 정의된 집합 Z는 가환환이다
  이 예에서는 이 집합을 R=<Z,+,*>로 나타낸다
- 덧셈은 단지 세 개의 성질을 만족한다
  곱셈은 또한 뎃셈 위에서 분배 법칙을 만족한다
  1. Closure(닫힘)
  2. Associativity(결합법칙)
  3. Commutativity(분배법칙)


<체(Field>
- F로 표기되는 체(Field)는 특정한 성질을 만족하는 두 개의 연산이 정의된 가환환이다
- 일반적인 가환환과 마찬가지로 첫번째 연산은 아벨군에 대해 요구되는 다섯 가지 성질을 모두 만족한다
- 두 번째 연산은 첫 번째 연산의 항등원이 역원을 갖지 않는다는 것을 제외하고 군의 모든 다섯 가지 성질을 만족한다
  1. Closure
  2. Associativity
  3. Commutativity
  4. Existence of identity
  5. Existence of inverse



<유한체(Finite Field)>
- 유한체(Finite Field)는 유한개의 원소를 갖고 있는 체이다
- 유한체는 암호에서 매우 중요한 구조
- 갈로아는 원소의 개수가 p^n인 유한개의 원소를 갖는 체가 존재함을 보였다(p는 소수이고, n은 양정수)
- 갈로아 체, GF(p^n)은 p^n개의 원소를 갖는 유한체이다



<체 GF(p)>
- n=1 일 때, GF(p)는 체이다
- 이 체는 두 개의 산술 연산(덧셈과 곱셈)을 갖고 있는 집합
  Zp={0,1,...,p-1}가 될 수 있다
- 암호 분야에서 가장 널리 쓰이는 체는 집합 {0,1}과 두 개의 연산, 덧셈과 곱셈을 갖고 있는 GF(2)형태이다



<요약(Summary)>
- 세 가지 대수적 구조의 연구는 덧셈/뺄셈과 곱셈/나눗셈 같은 비슷한 연산이 정의된 집합들을 사용할 수 있도록 해준다
- 세 구조들 사이를 구별할 필요가 있다
  - 군은 하나의 연관된 연산들의 쌍을 지원
  - 환은 하나의 연관된 연산들의 쌍과 하나의 독립적인 연산을 지원
  - 체는 연산들의 두 쌍을 지원

Algebraic Structure   Supported Typical Operations   Supported Typical Sets of Integers
     1. Group                  (+ -) or (X +)                       Zn or Zn*
     2. Ring                    (+ -) and (X)                        Z
     3. Field                    (+ -)and(X +)                       Zp