Factoring polynomials over finite fields has influenced on many areas of computer science and computational mathematics such as computer algebra, algebraic coding theory, computational number theory, cryptography. In cryptography there are numerous examples. Index calculus method for computing the discrete logarithms over finite fields. Finding roots of polynomial for the same problem in order to establish ismorphisms between different representations of the same field. computing the number of points on elliptic curves, building arithmetic public key cryptosystem, designing cyclic redundancy code, studying decoding algorithm for algebraic code such as BCH code.
이 논문에서는 유한체 상에서의 임의의 다항식 인수분해 하는 방법에 대해 알아본다. 이 인수분해는 부호이론, 타원 곡선, 암호시스템 등에서 활용된다. 우선 최대공약수 계산만으로 인수를 찾아낼 수 있다는 장점이 있는 Berlekamp의 방법이 있다. 하지만 Berlekamp의 방법은 체가 큰 경우에는 그 만큼 계산량이 많아야 한다는 단점도 있다. 그래서 계산량을 줄일 수 있는 다른 방법이 요구된다. ZassenHaus의 방법처럼 새로운 다항식을 생성해서 그 다항식의 근에 대해서만 최대공약수 계산을 하는 방법이 있고, DDF와 EDF 방법도 있다. 그리고 Mobius inversion formula 를 이용하여 n차 모든 기약다항식들의 곱인 $V_n$(x) 가 cyclotomic 다항식들의 곱으로 표현된다는 것을 알 수 있다. 따라서 cyclotomic 다항식이 비록 특정한 형태의 다항식이기는하지만 cyclotomic 다항식을 인수분해 할 수 있다는 것은 $V_n$(x) 를 인수분해할 수 있다는 것을 의미하고, 그 것은 곧 모든 n차 기약다항식을 알 수 있다는 것을 의미한다.
