삼항 다항식을 이용한 효율적인 비트-병렬 구조의 곱셈기

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 13권 / 5호 / 179 ~ 187페이지
· 저자명 : 정석원, 이선옥, 김창한

초록

최근 빠른 하드웨어의 구현은 속도의 효율성을 중시하는 환경에서 큰 관심의 대상이 되고 있다. 유한체 연산기는 연산과정이 복잡한 곱셈 연산에 의해 속도가 결정된다. 연산 수행 속도를 빠르게 개선하기 위해 본 논문에서는 하드웨어 구조를 기존의 Mastrovito방법을 이용하여 제안하고자 한다. 삼항기약다항식(trinomial) 를 이용하여 제안하는 곱셈기의 시간 복잡도를 기존의 복잡도[14] 에서 으로 감소시킨다. 그러나 공간 복잡도를 살펴보면 AND 게이트 수가 기존의 복잡도와 으로 같지만, XOR 게이트의 수는 기존 복잡도[14]인 에서 으로 기약다항식의 중간항 차수인 에 따라 약간 증가된다. 기약다항식의 최고차 항을 표준에서 권장하는 차수와 그에 준하는 다항식의 차수에 대해 XOR 공간 복잡도가 평균적으로 1.18% 증가하는 데 비해, 시간 복잡도는 평균적으로 9.036% 정도 감소한다.

참고자료

· 없음