삼항 기약다항식을 위한 효율적인 Shifted Polynomial Basis 비트-병렬 곱셈기 (Efficient Bit-Parallel Shifted Polynomial Basis Multipliersfor All Irreducible Trinomial)

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 19권 / 2호 / 49 ~ 61페이지
· 저자명 : 장남수, 김창한, 홍석희, 박영호

초록

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

영어초록

Finite Field multiplication operation is one of the most important operations in the finite field arithmetic. Recently, Fan and Dai introduced a Shifted Polynomial Basis(SPB) and construct a non-pipeline bit-parallel multiplier for . In this paper, we propose a new bit-parallel shifted polynomial basis type I and type II multipliers for defined by an irreducible trinomial . The proposed type I multiplier has more efficient the space and time complexity than the previous ones. And, proposed type II multiplier have a smaller space complexity than all previously SPB multiplier(include our type I multiplier). However, the time complexity of proposed type II is increased by 1 XOR time-delay in the worst case.

참고자료

· 없음