상세정보
학술지
Low Space Complexity GF (2m) Multiplier for Trinomials Using n-Term Karatsuba Algorithm
- 저자
- 박선미, 장구영, 홍도원, 서창호
- 발행일
- 201902
- 출처
- IEEE Access, v.7, pp.27047-27064
- ISSN
- 2169-3536
- 출판사
- IEEE
- 협약과제
- 19ZH1200, 데이터 안심사회를 위한 트러스트 데이터 커넥톰 핵심 원천 기술 개발, 박종대
- 초록
- We propose bit-parallel GF(2{m}) multipliers for irreducible trinomials using an n -term Karatsuba algorithm and Mastrovito approach, which are generalizations of the newly proposed multiplication scheme for a specific trinomial. The complexities of the proposed multipliers for GF(2{m}) depend on the choice of an irreducible trinomial x{m}+x{k}+1 defining GF(2{m}) and values n , m-{0} such that m=nm-{0} or m=nm-{0}+1. It is possible to achieve a space-time tradeoff by choosing proper values for k,~n , and m-{0}. For the purpose of a specific comparison, we compare the proposed multipliers with the best-known multipliers for an odd m\in [{399,450}] for which there exists an irreducible trinomial of degree m. As a result, the proposed multipliers achieve the lowest space complexities among similar bit-parallel multipliers (they have roughly 40% reduced space complexities compared with the fastest multiplier). On the other hand, their time complexities match or are at most 2T-{X} higher than the fastest multipliers, where T-{X} is the delay of one 2-input XOR gate.
- KSP 제안 키워드
- Bit-parallel, Karatsuba algorithm, Sampling Time(Ts), Space Complexity, Space time(ST), XOR gate