확장체 GF($p^n$)의 구성에서 차수와 다항식 곱셈 방법은 밀접한 관련을 가진다. 기존의 다항식 곱셈 방법인 KO] 및 MSK 방법은 효율적으로 계수-곱셈 연산량을 줄인다. 그러나 이들 방법을 이용하여 확장체 곱셈을 구성할 경우, 일반적으로 해당하는 분할 방법의 배수가 되도록 패딩(Padding)하여 구성하지만 이에 대한 기준이 모호하며 계수-곱셈의 연산량이 최소가 되도록 패딩하는 방법 또한 제안되지 않았다. 본 논문에서는 확장체 곱셈을 효율적으로 구성할 수 있는 기본적인 성질과 계수-곱셈의 연산량이 최소가 되는 다항식 차수를 찾는 알고리즘을 제안한다. 본 논문에서 제안하는 알고리즘을 적용하면 기존의 방법을 그대로 적용하여 구성할 때 보다 확장체의 차수가 증가할수록 더 많은 계수-곱셈 연산량을 줄일 수 있다. 따라서 본 논문의 결과는 스마트 카드 등 작은 공간 복잡도를 요구하는 병렬처리 곱셈기에 효율적으로 적용될 수 있다.
In the construction of an extension field, there is a connection between the polynomial multiplication method and the degree of polynomial. The existing methods, KO and MSK methods, efficiently reduce the complexity of coefficient-multiplication. However, when we construct the multiplication of an extension field using KO and MSK methods, the polynomials are padded with necessary number of zero coefficients in general. In this paper, we propose basic properties of KO and MSK methods and algorithm that can reduce coefficient-multiplications. The proposed algorithm is more reducible than the original KO and MSK methods. This characteristic makes the employment of this multiplier particularly suitable for applications characterized by specific space constrains, such as those based on smart cards, token hardware, mobile phone or other devices.
