장남수, 김창한, 홍석희, 박영호,

Vol. 19, No. 2, pp. 49-62, 4월. 2009
10.13089/JKIISC.2009.19.2.49, Full Text:
Keywords: Shifted Polynomial Basis, Irreducible Trinomial, Mastrovito Multiplier, Bit-Parallel Multiplier
Abstract

유한체 연산중에서 곱셈 연산은 중요한 연산중 하나이다. 또한, 최근에 Fan과 Dai는 이진체 곱셈기의 효율성을 개선하기 위하여 Shifted Polynomial Basis(SPB)와 이를 이용한 non-pipeline 비트-병렬 곱셈기를 제안하였다. 본 논문에서는 삼항 기약다항식 $x^{n}+x^{k}+1$에 의하여 정의된 $F_{2^n}$ 위에서의 새로운 SPB 곱셈기 type I과 type II를 제안한다. 제안하는 type I 곱셈기는 기존의 SPB 곱셈기에 비하여 시간 및 공간 복잡도면에서 모두 효율적이다. 그리고 type II 곱셈기는 제안하는 type I 곱셈기를 포함하여 기존의 모든 결과보다 작은 공간 복잡도를 가진다. 그러나 type II 곱셈기의 시간 복잡도는 n과 k에 따라 최대 1 XOR time-delay 증가한다.

Statistics
Cite this article