Efficient Semi-systolic AB2 Multiplier over Finite Fields

Kim Keewon

doi:https://doi.org/10.9708/jksci.2020.25.01.037

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2020, 25(1), pp.37-43
DOI :https://doi.org/10.9708/jksci.2020.25.01.037
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Kim Keewon ¹

¹ 단국대학교

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.
KEYWORDS

Finite fields , Multiplication , Shifted polynomial basis , Semi-systolic array , Cryptography
REFERENCES (23)

[book] A. J. Menezes / 1996 / Handbook of Applied Cryptography / CRC Press

[book] R. Lidl / 1994 / Introduction to Finite Fields and Their Applications / Cambridge University Press

[journal] Chin-Liang Wang / 1991 / Systolic array implementation of multipliers for finite fields GF(2/sup m/) / IEEE Transactions on Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 38 (7) : 796~800 / 10.1109/31.135751

[journal] C. S. Yeh / 1984 / Systolic Multipliers for Finite Fields / IEEE Transactions on Computers / Institute of Electrical and Electronics Engineers (IEEE) C-33 (4) : 357~360 / 10.1109/TC.1984.1676441

[journal] Chiou-Yng Lee / 2005 / Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2/sup m/) / IEEE Transactions on Computers / Institute of Electrical and Electronics Engineers (IEEE) 54 (9) : 1061~1070 / 10.1109/TC.2005.147

[journal] C. W. Chiou / 2006 / Concurrent Error Detection in Montgomery Multiplication over GF(2m) / IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E89-A (2) : 566~574 / 10.1093/ietfec/e89-a.2.566

[journal] W.-T. Huang / 2010 / Concurrent error detection and correction in a polynomial basis multiplier over GF(2m) / IET Information Security / Institution of Engineering and Technology (IET) 4 (3) : 111~ / 10.1049/iet-ifs.2009.0160

[journal] Kee-Won Kim / 2013 / A low latency semi-systolic multiplier over GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 10 (13) : 20130354~20130354 / 10.1587/elex.10.20130354

[journal] Se-Hyu Choi / 2014 / Low complexity semi–systolic multiplication architecture over GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 11 (20) : 20140713~20140713 / 10.1587/elex.11.20140713

[journal] Kee-Won Kim / 2015 / A Semi-systolic Montgomery Multiplier over GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 12 (21) : 20150769~20150769 / 10.1587/elex.12.20150769

[journal] 김기원 / 2016 / Low Latency Systolic Multiplier over GF(2m)Using Irreducible AOP / 대한임베디드공학회논문지 / 대한임베디드공학회 11 (4) : 227~233 / http://dx.doi.org/10.14372/IEMEK.2016.11.4.227

[journal] Se-Hyu Choi / 2017 / Reduced complexity polynomial multiplier architecture for finite fields GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 14 (17) : 20160797~20160797 / 10.1587/elex.14.20160797

[journal] Kee-Won Kim / 2019 / Low-latency semi-systolic architecture for multiplication over finite fields / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 16 (10) : 20190080~20190080 / 10.1587/elex.16.20190080

[journal] Kee-Won Kim / 2017 / Efficient Unified Semi-systolic Arrays for Multiplication and Squaring over GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 14 (12) : 20170458~20170458 / 10.1587/elex.14.20170458

[journal] Kee-Won Kim / 2018 / Efficient Bit-parallel Systolic Architecture for Multiplication and Squaring over GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 15 (2) : 20171195~20171195 / 10.1587/elex.14.20171195

[journal] Atef Ibrahim / 2019 / Efficient Parallel Semi-systolic Array Structure for Multiplication and Squaring in GF(2m) / IEICE Electronics Express / Institute of Electronics, Information and Communications Engineers (IEICE) 16 (12) : 20190268~20190268 / 10.1587/elex.16.20190268

[journal] Shyue-Win Wei / 1994 / A systolic power-sum circuit for GF(2/sup m/) / IEEE Transactions on Computers / Institute of Electrical and Electronics Engineers (IEEE) 43 (2) : 226~229 / 10.1109/12.262128

[journal] Jyh-Huei Guo / 2000 / New Systolic Arrays for C+AB2, Inversion, and Division in GF(2m) / IEEE Transactions on Computers / Institute of Electrical and Electronics Engineers (IEEE) 49 (10) : 1120~1125 / 10.1109/12.888047

[journal] Kee-Won Kim / 2013 / Low-complexity Parallel and Serial Systolic Architectures for AB2 Multiplication in GF(2m) / IETE Technical Review / Medknow 30 (2) : 134~141 / 10.4103/0256-4602.110552

[journal] S.‐H. Choi / 2016 / Parallel in/out Systolic AB2 Architecture with Low Complexity in GF(2m) / Electronics Letters / Institution of Engineering and Technology (IET) 52 (13) : 1138~1140 / 10.1049/el.2015.3681

[journal] 김태완 / 2017 / Low-latency Montgomery AB2 Multiplier Using Redundant Representation Over GF(2m) / 대한임베디드공학회논문지 / 대한임베디드공학회 12 (1) : 11~18 / http://dx.doi.org/10.14372/IEMEK.2017.12.1.11

[journal] Haining Fan / 2005 / Fast Bit-Parallel GF(2^n) Multiplier for All Trinomials / IEEE Transactions on Computers / Institute of Electrical and Electronics Engineers (IEEE) 54 (4) : 485~490 / 10.1109/TC.2005.64

[journal] Haining Fan / 2006 / Fast Bit Parallel Shifted Polynomial Basis Multipliers in GF(2n) / IEEE Trans. Circuits Syst. I: Fundam. Theory Appl / Institute of Electrical and Electronics Engineers (IEEE) 53 (12) : 2606~2615 / 10.1109/TCSI.2006.883855
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools