[이산수학] Equivalance Relation R, Characteristic, Galois Field

F[x]에 속한 다항식 zero polynomial 이 아닌 s(x)가 있다. 
$f(x) - g(x) = t(x) s(x)$ 인 다항식 $t(x) \in F[x]$ 가 있을 때 이는 s(x)가 f(x) - g(x)를 나눈다는 뜻이 된다.
이를 f(x) R g(x) 로 표현하며 F[x]에 대해 Equivalance Relation(동치 관계)라고 한다.
$\mathbf{f(x) \equiv g(x) \ (mod \ s(x))} $ 모듈로 s(x)에 대해 동치이다.

• 이를 통해 다항식 집합을 나눌 수 있다. 

Equivalance Classes for R

$s(x) = x^2 + x + 1 \in Z_2[x]$ 일 때,

나올 수 있는 Equivalance Classes는 4개가 된다. -> $Z_2$는 정수 집합으로 {0, 1}을 가지고 있기 때문에

• [0] : x의 계수가 0이고 상수항도 0인경우 $ = \{t(x)(x^2 + x + 1) \ | \ t(x) \in Z_2[x] \}$
• [1] : x의 계수가 0이고 상수항이 1인 경우 $ = \{t(x)(x^2 + x + 1) + {\color{DarkGreen} 1} \ | \ t(x) \in Z_2[x] \}$
• [x] : x의 계수가 1이고 상수항이 0인 경우 $ = \{t(x)(x^2 + x + 1) + {\color{DarkGreen} x} \ | \ t(x) \in Z_2[x] \}$
• [x + 1] : x의 계수가 1이고 상수항도 1인 경우  $ = \{t(x)(x^2 + x + 1) + {\color{DarkGreen} {x + 1}}\ | \ t(x) \in Z_2[x] \}$

class의 수는 다음과 같은 공식으로 얻을 수 있다.

$$ 4 = 2^2 = |Z_2|^{deg[s(x)} $$

 

operation

F[x] 집합에 속하는 f(x), g(x), s(x)에 대해

• [f(x)] + [g(x)] = [f(x) + g(x)] : 덧셈 후 모듈러 연산 = 모듈러 연산 후 덧셈
• [f(x)][g(x)] = [f(x)g(x)]  = [r(x)]
  • f(x)g(x) = q(x)s(x) + r(x) 이기 때문에 양변에 모듈러 s(x)를 취해주면 $ f(x)g(x) \equiv r(x) \ (mod \ s(x)) $ 가 된다. 

F[x] / s(x)

F[x]에서 modulo s(x)에 대한 equivalance classes

 

$s(x) = x^2 + x + 1$에 대해 $Z_2[x] / s(x) \equiv \{[0], [1], [x], [x+1]\}$ 이다.

• 여기서 +의 항등원은 0이고 역원은 자기 자신이다. 
• *의 항등원은 1이고 모든 원소에 대해 항등원이 존재한다. -> 역원이 있다. 
  • zero divisor가 없기 때문에 integral domain이며, 모든 원소가 unit이기 때문에 field이다. 

1. F[x]/s[x] 는 commutative ring with unity이다.
2. s(x)가 F[x]에서 irreducible이면 F[x]/s[x]는 field이다.
3. |F| = q 그리고 deg[s(x)] = n일 때 F[x]/s[x]는 $\mathbf{{\color{DarkGreen} {q^n}}}$개의 원소를 가진다.

 

 

 

Characteristic of Ring

R에 속하는 모든 원소 r에 대해 nr = z를 만족하는 가장 작은 양의 정수 n
R이 characeristic n을 가졌다고 하고, Char(R) = n 이라고 쓴다. 
이런 n이 존재하지 않을 경우 R은 characteristic 0을 가진다고 한다. 

• group의 ord는 특정 원소에서 정의된다. ex) $Z_6$ 에서 ord(2) = 3
• Char은 모든 원소에 대해 ex) Char($Z_6$) = 6 => 모든 원소를 6번 더하면 0이 나온다.
• ring $(Z_n, +, \cdot)$ 은 characteristic n을 갖는다. 
• $(Z, +, \cdot), (Q, +, \cdot)$ 는 characteristic 0을 갖는다.
• ring이 무한이여도 양의 characteristic이 가능하다. ex) $Z_3[x]$는 무한한 다항식 ring이지만 3번 더하면 항상 0이다.
• 차수와 characteristic은 다를 수 있다. ex) $|Z_2[x] / (x^2 + x + 1) | = 4$ 이지만 2의 characteristic을 가진다.

 

Characteristic of Field 

$(F, +, \cdot)$ 은 char(F)가 0보다 큰 값을 가지면 char(F)의 값이 소수이다.

 

• F가 field이고 m = |F| 이면, F에 속한 모든 원소 a에 대해 ma = z가 된다.-> |F|가 소수이기 때문에 characteristic 또한 소수가 된다. 
• $(Z_p, +, \cdot)$ : characteristic p
• $Z_2[x] / (x^2 + x + 1)$ : characteristic 2
• $Z_3[x] / (x^2 + x + 1)$ : charecteristic 3

 

Galois of Field 

유한한 field F는 order $p^t$를 가진다. 여기서 p는 소수이고 t는 양의 정수이다.
$p^t$의 크기를 가지는 유한한 field를 $GF(p^t)$ 로 표현할 수 있으며 이를 Galois field라고 한다.

• 만약 |F| = q이고 deg[s(x)] = n일 때 F[x] / s(x) 는 $q^n$개의 원소를 가지고 있다.
  
  • $(F, +, \cdot)$ 이 field이고 char(F) > 0이면, 그 값은 prime
• $p^t$의 크기를 갖는 field는 유일하다. 
  • 같은 크기를 가지고 있는 두 field는 isomorphic이기 때문에

GF($2^8$) vs Polynomial

8차 다항식과 비트를 8개 가지고 있는 이진수는 isomorphic 이다.

• 01010111 <-> $x^6 + x^4 + x^2 + 1$
• Polynomial Addiction : XOR 연산
  • $(x^6 + x^4 + x^2 + x + 1) + (x^7 + x^4 + x^3 + x + 1) = (x^7 + x^6 + x^3 + x^2)$
  • 01010111 ^ 10011011 = 11001100
• irreducible 다항식 m(x) = $x^8 + x^4 + x^3 + x + 1$ -> AES에서 모듈로 역할을 한다.
• Polynomial Multiplication은 간단한 연산이 없다.
  • 다른 다항식과 곱셈을 수행하고 m(x)로 나머지를 구한다.