ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

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

상세정보

학술지 Efficient Bit-Parallel Multiplier for All Trinomials Based on n-Term Karatsuba Algorithm
Cited 2 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
저자
박선미, 장구영, 홍도원, 서창호
발행일
202009
출처
IEEE Access, v.8, pp.173491-173507
ISSN
2169-3536
출판사
IEEE
DOI
https://dx.doi.org/10.1109/ACCESS.2020.3023804
협약과제
20ZR1300, 지능형 사이버 보안 및 신뢰 인프라 기술 연구, 김익균
초록
Recently, hybrid multiplication schemes over the binary extension field GF(2m) based on nterm Karatsuba algorithm (KA) have been proposed for irreducible trinomials. Their complexities depend on a decomposition of m and the choice of a generation polynomial. However, these multipliers have some limitations on a decomposition of m or generation polynomial xm + xk + 1 such that m ?돟 2k. In this paper, we loosen such limited conditions. We present a new hybrid bit-parallel multiplier based on n-term KA for any irreducible trinomial xm + xk + 1 (0 < k < m), where m is decomposed as m = nm0 + r with 0 < r < m0 and 1 < n. (Here, various values for n, m0 and r may be chosen.) To this end, we generalize the previously proposed multiplication scheme for xnm0+1 +xk +1 into xnm0+r +xk +1. We evaluate the explicit complexity of the proposed multiplier. Specific comparisons show that the proposed multiplier achieves the lowest space complexity with the same or lower time complexity among hybrid multipliers. Compared to the fastest multipliers, the time complexity of the proposed multiplier costs only TX higher while its space complexity is much lower (it has roughly 40% reduced space complexity), where TX is the delay of one 2-input XOR gate.
키워드
Hybrid bit-parallel multiplier, Karatsuba algorithm, Mastrovito approach, Shifted polynomial basis, Trinomial
KSP 제안 키워드
Bit-parallel multiplier, Extension field, Karatsuba algorithm, Shifted polynomial basis(SPB), Space Complexity, Time Complexity, XOR gate