다항식, 생성원 사용하기

<GF(2^n) FIELDS>
- 암호에서는 자주 네 개의 연산(덧셈, 뺄셈, 곱셈, 나눗셈)을 필요로한다
  다시 말해서, 암호에는 체가 필요하다
- 그러나 컴퓨터에서 체에 정의된 연산을 수행할 때, 양의 정수들은 컴퓨터에 n-비트 워드들로 저장된다
- N은 보통 8, 16, 32, 63 등의 배수형태를 취한다
  이것은 정수들의 범위가 0에서 (2^n)-1 까지인 것을 의미한다. 즉, 모듈러는 2^n
- 따라서 체를 사용할 때는 두 가지 방법이 있다
- n-bit 워드들을 표현하는 다항식들은 두 개의 체 GF(2)와 GF(2^n)를 사용한다



<Modulus>
- GF(2^n)의 다항식들의 집합들에 대해서,
  차수 n의 다항식의 어떤 집합은 군의 모듈러로서 정의된다
- 이 경우 모듈러는 소수 다항식(prime polynomial)으로서 행동하는데 다항식은 집합에서 이 다항식을 
  나누는 낮은 차수의 다항식이 없는 다항식을 의미한다
- 소수 다항식은 보다 작은 차수들의 다항식으로 분해될 수 없다
- 이런 다항식을 기약 다항식(irreducible polynomial)이라고 한다



<곱셈(Multiplication)>
- 계수 곱셈은 GF(2)에서 이루어진다
- x^i에서 x^j를 곱하면 결과로 x^(i+j)을 얻는다
- 곱셈은 n-1보다 큰 차수를 가지는 항을 생성할 수도 있다
  따라서 모듈러 다항식을 사용하여 곱셈한 결과를 줄일 필요가 있다


<컴퓨터를 사용한 곱셈(Multiplication Using Computer)>
- 나눗셈 연산 때문에 두 다항식을 곱하기 위한 프로그램을 개발하는데 포함되는 효율적인 알고리즘이 존재
- 컴퓨터의 구현에서는 x에 의해 줄여진 다항식을 반복적으로 곱하는 더 좋은 알고리즘을 사용한다



<Using a Generator>
- 떄로는 GF(2^n)의 원소를 정의할 때 생성원을 이용하는 것이 더 편리할 때가 있다
- 기약 다항식 f(x)가 정의된 체에서, 생성원 g에 대하여 f(g)=0로 가정
  {0, g, g, g^2, ..., g^N}, where N = (2^n)-2 (단, 생성원(generator))



<Summary>
- 유한체 GF(2^n)은 n-비트 워드들에 대한 
  덧셈, 뺄셈, 곱셈, 나눗셈의 네 개의 연산들을 정의하기 위해 사용될 수 있다
- 유한체에서는 0에 의한 나눗셈을 제외한 모든 연산을 사용할 수 있다