ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Space Efficient GF (2m) Multiplier for Special Pentanomials Based on n-Term Karatsuba Algorithm
Cited 1 time in scopus Download 22 time Share share facebook twitter linkedin kakaostory
저자
박선미, 장구영, 홍도원, 서창호
발행일
202002
출처
IEEE Access, v.8, pp.27342-27360
ISSN
2169-3536
출판사
IEEE
DOI
https://dx.doi.org/10.1109/ACCESS.2020.2971702
협약과제
20ZR1300, 지능형 사이버 보안 및 신뢰 인프라 기술 연구, 김익균
초록
Recently, new multiplication schemes over the binary extension field GF(2^{m}) based on an n -term Karatsuba algorithm have been proposed for irreducible trinomials. In this paper, we extend these schemes for trinomials to any irreducible polynomials. We introduce some new types of pentanomials and propose multipliers for those pentanomials utilizing the extended schemes. We evaluate the rigorous space and time complexities of the proposed multipliers, and compare those with similar bit-parallel multipliers for pentanomials. As a main contribution, the best space complexities of our multipliers are \frac {1}2m^{2}+O\left({m^{\frac {3}2}}\right) AND gates and \frac {1}2m^{2}+O\left({m^{\frac {3}2}}\right) XOR gates, which nearly correspond to the best results for trinomials. Also, specific comparisons for three fields GF(2^{163}) , GF(2^{283}) , and GF(2^{571}) recommended by NIST show that the proposed multiplier has roughly 40% reduced space complexity compared to the fastest multipliers, while it costs a few more XOR gate delay. It is noticed that our space complexity gain is much greater than the time complexity loss. Moreover, the proposed multiplier has about 21% reduced space complexity than the best-known space efficient multipliers, while having the same time complexity. The results show that the proposed multipliers are the best space optimized multipliers.
키워드
Bit-parallel multiplier, Karatsuba algorithm, Mastrovito approach, Pentanomial, Shifted polynomial basis
KSP 제안 키워드
Bit-parallel multiplier, Extension field, Karatsuba algorithm, Shifted polynomial basis(SPB), Space Complexity, Three fields, Time Complexity, XOR gate, gate delay
본 저작물은 크리에이티브 커먼즈 저작자 표시 (CC BY) 조건에 따라 이용할 수 있습니다.
저작자 표시 (CC BY)