유한체위에서 정규기저의 고속생성과 저비용 연산 알고리즘의 구현에 관한 연구

On Implementations of Algorithms for Fast Generation of Normal Bases and Low Cost Arithmetics over Finite Fields

유한체위에서 사칙연산의 H/W 구현의 효율성은 사용하는 유한체의 기저 선택에 의해서 크게 좌우된다. 그러한 H/W 구현의 효율성의 관점에서 보면, 정규기저가 가장 적절한 이유는, 표수가 2인 유한체GF(2n)의원소를 ？㎀？ ？煬？GF(2n)？堧㎰【？ 정규기저로 표현하면, 원소의 제곱은 단순하게 좌표의 순환이동이 되기 때문이다. 본 논문에서는, 모든 유한체에서 관용기저로 부터 정규기저로 고속으로 변환하는 알고리즘을 소개하였으며 그 알고리즘을 이용한 H/W 구현결과와 우리의 방법으로 구현한 정규기저를 이용하여, 유한체 GF(2n)위에서 두 원소의 곱셈과 역원을 구하는 효율적인 알고리즘에 따른 프로그램과 H/W 구현결과를 제시하였다.

The efficiency of implementation of the arithmetic operations in finite fields depends on the choice representation of elements of the field. It seems that from this point of view normal bases are the most appropriate, since raising to the power 2 of characteristic 2 is reduced in these bases to a cyclic shift of the coordinates. We, in this paper, introduce our algorithm to transform fastly the conventional bases to normal bases and present the result of H/W implementation using the algorithm. We also propose our algorithm to calculate the multiplication and inverse of elements with respect to normal bases in and present the programs and the results of H/W implementations using the algorithm.