유한체상의 효율적인 세미-시스톨릭 AB2 곱셈기
Efficient Semi-systolic AB2 Multiplier over Finite Fields
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 논문에서는 유한체상의 SPB(shifted polynomial basis)를 사용한 효율적인 AB2 곱셈 알고리즘을 제안한다. SPB의 특징을 이용하여, AB2 곱셈을 위한 수식을 두 부분으로 분할하였다. 분할된두 수식은 동시에 실행가능하며, 이를 병렬로 처리하는 알고리즘을 도출하였다. 그리고 제안한 알고리즘을 기반으로 효율적인 세미-시스톨릭(semi-systolic) AB2 곱셈기를 제안한다. 제안한 곱셈기는기존의 곱셈기에 비해 낮은 공간-시간 복잡도(area-time complexity)를 가진다. 기존의 구조들과 비교하면, 제안한 AB2 곱셈기는 공간-시간 복잡도면에서 Wei, Wang-Guo, Kim-Lee, 및 Choi-Lee의 곱셈기들의 약 94%, 87%, 86%, 및 83% 가량이 감소되었다. 따라서 제안한 곱셈기는 VLSI(very large scale integration) 구현에 적합하며 다양한 응용의 기초적인 구성 요소로 쉽게 적용할 수 있다.
Abstract
In this paper, we propose an efficient AB2 multiplication algorithm using SPB(shifted polynomial basis) over finite fields. Using the feature of the SPB, we split the equation for AB2 multiplication into two parts. The two partitioned equations are executable at the same time, and we derive an algorithm that processes them in parallel. Then we propose an efficient semi-systolic AB2 multiplier based on the proposed algorithm. The proposed multiplier has less area-time (AT) complexity than related multipliers. In detail, the proposed AB2 multiplier saves about 94%, 87%, 86% and 83% of the AT complexity of the multipliers of Wei, Wang-Guo, Kim-Lee, Choi-Lee, respectively. Therefore, the proposed multiplier is suitable for VLSI implementation and can be easily adopted as the basic building block for various applications.
참고문헌 (23)
- A. J. Menezes, "Handbook of Applied Cryptography" (1996), CRC Press
- R. Lidl, "Introduction to Finite Fields and Their Applications" (1994), Cambridge University Press
- Chin-Liang Wang, "Systolic array implementation of multipliers for finite fields GF(2", sup m, IEEE Transactions on Circuits and Systems, pp.1991, 38(7)[DOI]
- C. S. Yeh, "Systolic Multipliers for Finite Fields", IEEE Transactions on Computers, C-33(4), pp.357~360 (1984), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
- Chiou-Yng Lee, "Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2", sup m, IEEE Transactions on Computers, pp.2005, 54(9)[DOI]
- C. W. Chiou, "Concurrent Error Detection in Montgomery Multiplication over GF(2m)", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A(2), pp.566~574 (2006)[DOI]
- W.-T. Huang, "Concurrent error detection and correction in a polynomial basis multiplier over GF(2m)", IET Information Security, 4(3), pp.111~ (2010), Institution of Engineering and Technology (IET)[DOI]
- Kee-Won Kim, "A low latency semi-systolic multiplier over GF(2m)", IEICE Electronics Express, 10(13), pp.20130354~20130354 (2013), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Se-Hyu Choi, "Low complexity semi–systolic multiplication architecture over GF(2m)", IEICE Electronics Express, 11(20), pp.20140713~20140713 (2014), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Kee-Won Kim, "A Semi-systolic Montgomery Multiplier over GF(2m)", IEICE Electronics Express, 12(21), pp.20150769~20150769 (2015), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- 김기원, "기약 AOP를 이용한 GF(2m)상의 낮은 지연시간의 시스톨릭 곱셈기", 대한임베디드공학회논문지, 11(4), pp.227~233 (2016), 대한임베디드공학회[DOI]
- Se-Hyu Choi, "Reduced complexity polynomial multiplier architecture for finite fields <i>GF<", i>(2<i><sup>m<, i>), pp.IEICE Electronics Express, 2017[DOI]
- Kee-Won Kim, "Low-latency semi-systolic architecture for multiplication over finite fields", IEICE Electronics Express, 16(10), pp.20190080~20190080 (2019), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Kee-Won Kim, "Efficient Unified Semi-systolic Arrays for Multiplication and Squaring over GF(2m)", IEICE Electronics Express, 14(12), pp.20170458~20170458 (2017), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Kee-Won Kim, "Efficient Bit-parallel Systolic Architecture for Multiplication and Squaring over GF(2m)", IEICE Electronics Express, 15(2), pp.20171195~20171195 (2018), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Atef Ibrahim, "Efficient Parallel Semi-systolic Array Structure for Multiplication and Squaring in GF(2m)", IEICE Electronics Express, 16(12), pp.20190268~20190268 (2019), Institute of Electronics, Information and Communications Engineers (IEICE)[DOI]
- Shyue-Win Wei, "A systolic power-sum circuit for GF(2", sup m, IEEE Transactions on Computers, pp.1994, 43(2)[DOI]
- Jyh-Huei Guo, "New Systolic Arrays for C+AB2, Inversion, and Division in GF(2m)", IEEE Transactions on Computers, 49(10), pp.1120~1125 (2000), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
- Kee-Won Kim, "Low-complexity Parallel and Serial Systolic Architectures for AB2 Multiplication in GF(2m)", IETE Technical Review, 30(2), pp.134~141 (2013), Medknow[DOI]
- S.‐H. Choi, "Parallel in", out Systolic AB2 Architecture with Low Complexity in GF(2m), 2016, pp.52(13), 1138~1140[DOI]
- 김태완, "GF(2m) 상의 여분 표현을 이용한 낮은 지연시간의 몽고메리 AB2 곱셈기", 대한임베디드공학회논문지, 12(1), pp.11~18 (2017), 대한임베디드공학회[DOI]
- Haining Fan, "Fast Bit-Parallel GF(2^n) Multiplier for All Trinomials", IEEE Transactions on Computers, 54(4), pp.485~490 (2005), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
- Haining Fan, "Fast Bit Parallel Shifted Polynomial Basis Multipliers in GF(2n)", IEEE Trans. Circuits Syst. I: Fundam. Theory Appl, 53(12), pp.2606~2615 (2006), Institute of Electrical and Electronics Engineers (IEEE)[DOI]