[부호이론] 5. Rudiments of Number Theory and Algebra

Number Theoretic Preliminaries

Euler Totient Function

Irreducible Polynomials and Extension Fields

Irreducible over R

만약 $f(x)=g(x)h(x)$ 꼴로 표현되지 않을 때, $f(x)$는 irreducible 하다고 한다.

$f(x), g(x), h(x) \in \mathbb{R[x]}$

Field extension

만약 Field $\mathbb{K}$가 Field $\mathbb{F}$의 subset이라면, $\mathbb{F}$는 $\mathbb{K}$의 extension field라 한다.

예를 들어, $\mathbb{C}$는 $\mathbb{R}$의 extension field이다.

• 여기서 한가지 재밌는 성질이 유도되는데, 만약 $GF(2)$에서 임의의 irreducible한 polynomial이 있을 때, 그 해를 $\alpha$라고 하자. 여기서 더 높은 차원의 Field Extension이 유도가 된다.

  $GF(2) \rightarrow GF(p^m)$

• irreducible polynomial은 차수별로 다 테이블로 정리가 되어있다. 교재를 보면 될 것.

Galois Fields

Characteristic

특정 Field 원소 하나만 갖고 덧셈을 반복했을 때 0이 나오는 최소값을 characteristic이라고 한다.

• 모든 Binary extension fields($GF[2^m]$)는 다 characteristic이 2이다.
• 모든 필드의 characteristic은 반드시 0이거나 소수여야 한다.
• 따라서 유한 필드 $GF(q)$는 언제나 $p$개의 필드 원소를 갖고 있게 된다.
• 또 따라서, 모든 $\mathbb{Z}_p$는 모두 $GF(q)$의 갈루아 필드이다.
• 또 여기서, $GF(p) \subseteq GF(q)$를 만족하는 $GF(p)$는 ground field라 불린다.

Order of field

• 그룹의 order는 그룹을 이루는 원소의 개수로 정의된다.
• 모든 유한 필드 $GF(q)$는 반드시 소수의 제곱수의 order를 갖게 된다.

Ground field

임의의 필드 $GF(p^m)$이 있을 때, $GF(p)$를 ground field라 한다.

• 만약 characteristic이 $p$인 필드 내에서 두 원소 $x, y$를 뽑는다고 할 때, 다음이 항상 성립한다.
  $(x+y)^p=x^p+y^p$
• 특히, $GF(2^m)$에 대해서는 다음이 성립한다.
  $(x+y)^2=x^2+y^2$

Cyclic structure (Multiplicative structure)

• $ord(\beta)$ 는 어떤 갈루아 필드 원소 $\beta$를 몇 번이나 곱해야 $1$로 돌아오는지를 나타낸다.

  앞서 봤던 Characteristic과 비슷하지만, 여기서는 덧셈이 아니라 곱셈에 대해서 정의된다.

• Primitive element는 이 원소만을 활용해서 모든 element를 만들 수 있는 원소로, $GF(q)$에 대해서 $q-1$인 경우는 언제나 primitive element이다.

• 따라서, 다음이 항상 성립한다.

  $ord(\beta)|(q-1)$

• 따라서, 다음이 항상 성립한다.

  $\beta^s=1\quad iif\quad ord(\beta)|s$

• 따라서, 다음이 항상 성립한다.
  만약 $ord(\alpha)=s$, $ord(\beta)=t$, $(s,t)=1$이면, $ord(\alpha \beta)=st$ 이다.

• 따라서, 다음이 항상 성립한다.
  만약 $ord(\alpha)=t, \beta=\alpha^i$ 이면, $ord(\beta)=t/(i,t)$이다.

• 필드 $\mathbb{F}$에서 정의된 degree $d$의 polynomial은 항상 최대 $d$개의 해를 갖고 있다.

• 갈루아 필드 $GF(q)$에 대해, 만약 $t|(q-1)$을 만족하는 t가 있다면, $GF(q)$ 내부에는 $\phi(t)$개 만큼의 order $t$ 원소가 있다.

• 갈루아 필드 $GF(q)$에는 $\phi(q-1)$개의 primitive elements가 있다.

• 갈루아 필드 $GF(q)$에 있는 모든 원소는 $x^q-x=0$ 방정식을 만족한다. 게다가, 이 방정식의 모든 해 집합은 그 갈루아 필드 원소들과 정확히 같다.

Splitting field

Splitting field(분할체)는 어떤 polynomial $f(x)\in \mathbb{F}[x]$의 해를 갖고 있는 가장 작은 확장 필드를 말한다.

• 모든 갈루아 필드 $GF(q)$ 내부의 모든 원소는 반드시 다음 방정식의 해가 된다.
  $x^{q^n}-x=0$

Subfields of Galois fields

• An element, $\beta \in GF(q^m)$ lies in $GF(q)$ if and only if $\beta^q=\beta$.
• $GF(q^k)$ is a subfield of $GF(q^j)$ if and only if $k|j$.

Irreducible and Primitive polynomials

• irreducible한 $m$차 polynomial $f(x) \in GF(p)[x]$는 반드시 $x^{p^m-1}-1$을 나눌 수 있다.
• irreducible한 $m$차 polynomial $f(x) \in GF(q)[x]$에 대해 $m|k$를 만족한다면, 다음이 만족된다.
  $f(x)|(x^{q^k}-x)$