Chapter 5. Finite Field

박병준·2022년 4월 11일

컴퓨터 보안

목록 보기

5/14

집합과 연산(·) 한 가지를 합쳐서 정의한다.
연산(·)이 덧셈인 경우 additive group이라고 부른다. 곱셈인 경우 multiplicative group.
Group은 하단의 A1~A4의 성질을 만족한다..
- (A1) Closure
  a와 b가 G에 속하면, a·b는 G에 속한다.
  집합의 원소와 관계가 있는 원소가 항상 그 집합에 속한다는 성질
- (A2) Associative(결합 법칙)이 성립
  a·(b·c)=(a·b)·c for all a, b, c in G
- (A3) Identity element(항등원)이 존재
  a가 G에 속할 때, a·e = e·a = a라면 e는 G에 속한다.
  항등원 e를 가지는 것
- (A4) Inverse element(역원)이 존재
  각 a가 G에 속할 때, a·a^−1 = a^−1·a = e를 만족하는 G에 속하는 a^−1가 있다.
  즉, 역원 a^−1을 가진다.
Abelian group
- (A5) Commutative(교환 법칙)이 성립하는 그룹
  a·b = b·a for all a, b in G
이러한 그룹이 유한개의 원소로 이루어져 있다면
-> finite group
무한개로 이루어졌다면
-> infinite group

그룹 연산자를 반복하여 exponentiation을 정의
a^3 = a·a·a
위 경우는 연산자를 곱셈으로 본 것
a^0 = e를 항등원이라고 정의한다.
a^−n = (a^')^n인 a'는 그룹 내 a의 역원이라고 정의한다.
a^−n을 a의 역원인 a^−1의 n승으로 나타낼 수 있다. -> (a^−1)^n
Cyclic Group: G에 속하는 어떤 원소 a가 a^k형태로 G의 모든 원소들을 나타낼 수 있으면, 해당 그룹을 Cyclic group이라고 부른다.
여기서 a는 G를 generate 한다고 하고, a를 G의 generator라고 부른다.
cyclic group은 항상 abelian이고 finite 또는 infinite하다.
cyclic group은 항상 교환 법칙이 성립할 수 밖에 없다.

모든 정수의 집합은 field가 아니다.
왜냐하면, 모든 원소가 곱셈의 역원을 가지는 것이 아니기 때문이다.

ex) 3의 덧셈에 대한 역원 -3은 정수들의 집합에 들어 있지만, 3의 곱셈에 대한 역원인 1/3은 집합에 들어가지 않는다.

Finite Field = Galois Field(GF)

f(x) = q(x)g(x) + r(x)
r(x): f(x)를 g(x)로 나눈 나머지
r(x) = f(x) mod g(x)
r(x)가 0이라면
g(x)|f(x)
g(x)를 f(x)의 factor(인자) 또는 divisor(약수)라고 할 수 있다.
다항식(polynomial) f(x)
"어떤 다항식 f(x)가 field에 대해 irreducible하다"의 뜻은 다음과 같다.
f(x)가 자기보다 작은 차수인 두 다항식의 곱으로 표현될 수 없다는 뜻
이 성질(irreducible polynomial)은 소수랑 비슷한 느낌이라 prime polynomial이라고도 부른다.

[GCD(a(x), b(x)) = c(x)]의 조건
c(x)는 a(x)와 b(x) 둘 다 나눈다.
a(x)와 b(x)의 모든 공약수는 c(x)의 약수이다.
Extended Euclidean algorithm을 이용하면 irreducible polynomial의 역원을 찾을 수 있다.
GF(2)이므로 모든 연산에 (mod 2)가 취해진다.
(mod 2)를 취하면
a+b (mod 2) = a-b (mod 2)이고, 이는 a XOR b와 같다.

출처
https://hororolol.tistory.com/451?category=897521
[Cryptography and Network Security: Principles and Practices]

뿌셔뿌셔