유한체상의 곱셈과 제곱을 위한 적은 면적의 비트-병렬 시스톨릭 어레이
Low-area Bit-parallel Systolic Array for Multiplication and Square over Finite Fields
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 논문은 유한체상의 곱셈과 제곱을 동시에 실행 가능한 알고리즘에서 공통적인 연산 부분을도출하고, 순차적인 처리를 통해서 하드웨어를 감소시키고 공간면에서 효율적인 비트-병렬 시스톨릭 어레이를 제안한다. 제안한 시스톨릭 어레이는 기존의 어레이에 비해 적은 공간 및 공간-시간복잡도(area-time complexity)를 가진다. 기존의 구조들과 비교하면, 제안한 시스톨릭 어레이는 공간복잡도면에서 Choi-Lee, Kim-Kim의 시스톨릭 어레이의 약 48%, 44% 감소되었으며, 공간-시간 복잡도면에서 약 74%, 44% 가량 감소되었다. 따라서 제안한 시스톨릭 어레이는 VLSI 구현에 적합하며 사물인터넷과 같이 하드웨어 제약이 있는 환경에서 기초적인 구성 요소로 적용할 수 있다.
Abstract
In this paper, we derive a common computational part in an algorithm that can simultaneously perform multiplication and square over finite fields, and propose a low-area bit-parallel systolic array that reduces hardware through sequential processing. The proposed systolic array has less space and area-time (AT) complexity than the existing related arrays. In detail, the proposed systolic array saves about 48% and 44% of Choi-Lee and Kim-Kim’s systolic arrays in terms of area complexity, and about 74% and 44% in AT complexity. Therefore, the proposed systolic array is suitable for VLSI implementation and can be applied as a basic component in hardware constrained environment such as IoT.
참고문헌 (21)
- A. J. Menezes, "Handbook of Applied Cryptography" (1996), CRC Press
- R. Lidl, "Introduction to Finite Fields and Their Applications" (1994), Cambridge University Press
- W.-T. Huang, "Concurrent error detection and correction in a polynomial basis multiplier over GF(2m)", IET Information Security, 4(3), pp.111~124 (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]
- 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, "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, "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]
- 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]
- P.A. Scott, "Architectures for exponentiation in GF(2", sup m, IEEE Journal on Selected Areas in Communications, pp.1988, 6(3)[DOI]
- Keon-Jik Lee, "Linear systolic multiplier", squarer for fast exponentiation, 2000, pp.76(3), 105~111[DOI]
- Jae-Cheol Ha, "A common-multiplicand method to the montgomery algorithm for speeding up exponentiation", Information Processing Letters, 66(2), pp.105~107 (1998), Elsevier BV[DOI]
- Se-Hyu Choi, "Efficient Systolic Modular Multiplier", squarer for Fast Exponentiation over GF(2m), 2015, pp.12(11), 20150222~20150222[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]
- K. W. Kim, "Efficient Combined Algorithm for Multiplication and Squaring for Fast Exponentiation over Finite Fields GF(2m)", Proceedings of the 7th International Conference on Emerging Databases, LNEE, 461, pp.50~57 (2017)
- 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]
- D. E. Knuth, "The Art of Computer Programming, Seminumerical Algorithms, Vol. II" (1997), Addison-Wesley