Efficient implementation of low time complexity and pipelined bit-parallel polynomial basis multiplier over binary finite fields



1 Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan, Iran

2 Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran

3 School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran


This paper presents two efficient implementations of fast and pipelined bit-parallel polynomial basis multipliers over GF (2m) by irreducible pentanomials and trinomials. The architecture of the first multiplier is based on a parallel and independent computation of powers of the polynomial variable. In the second structure only even powers of the polynomial variable are used. The parallel computation provides regular and low-cost structure with low critical path delay. In addition, the pipelining technique is applied to the proposed structures to shorten the critical path and to perform the computation in two clock cycles. The implementations of the proposed methods over the binary extension fields GF (2163) and GF (2233) have been successfully verified and synthesized using Xilinx ISE 11 by Virtex-4, XC4VLX200 FPGA.


[1] Arash Reyhani-Masoleh, "A New Bit-Serial Architecture for Field Multiplication Using Polynomial Bases", Cryptographic Hardware and Embedded Systems-CHES 2008, Vol. 5154, pp. 300-314.

[2] Che-Wun Chiou and Huey-Lin Jeng, "Parallel Algorithm for Polynomial Basis Multiplier in GF(2m) Fields", Tamkang Journal of Science and Engineering, Vol. 11, No. 2, 2008, pp. 211-218.

[3] XIE Jia-feng, HE Jian-jun, GUI Wei-hua, "Low latency systolic multipliers for finite field GF(2m) based on irreducible polynomials", Journal of Central South University, Vol. 19, Iss. 5, 2012, pp. 1283-1289.

[4] Huapeng Wu, "Bit-Parallel Finite Field Multiplier and Squarer Using Polynomial Basis", IEEE Transactions on Computers, Vol. 51, No. 7, July 2002, pp. 750-758.

[5] Eduardo Cuevas-Farfan, Miguel Morales-Sandoval, Alicia Morales-Reyes, Claudia Feregrino-Uribe, Ignacio Algredo-Badillo, Paris Kitsos, René Cumplido, "Karatsuba-Ofman Multiplier with Integrated Modular Reduction for GF(2m)", Advances in Electrical and Computer Engineering, Vol. 13, No. 2, 2013, pp. 3-10.

[6] M. Elia, M. Leone and C. Visentin, "Low complexity bit-parallel multipliers for GF (2m) with generator polynomial P(x) = xm + xk + 1", Electronics Leters 1st April 1999 Vol. 35 No. 7, pp. 551-552.

[7] Nam Su Chang, Chang Han Kim, Young-Ho Park, and Jongin Lim, "A Non-redundant and Efficient Architecture for Karatsuba-Ofman Algorithm", Proceedings of the 8th International Conference on Information Security (ISC), Singapore, September 20-23, Springer-Verlag Berlin Heidelberg, Vol. 3650, 2005, pp. 288-299.

[8] Mario Alberto García-Martínez, Rubén Posada- Gómez, Guillermo Morales-Luna and Francisco Rodríguez-Henríquez, "FPGA Implementation of an Efficient Multiplier over Finite Fields GF(2m)", Proceedings of the IEEE International Conference on Reconfigurable Computing and FPGAs, 2005, pp.21-26.

[9] Chester Rebeiro and Debdeep Mukhopadhyay, "Hybrid Masked Karatsuba Multiplier for GF (2233)", 11th IEEE VLSI Design and Test Symposium, Kolkata, August 2007.

[10] Che Wun Chiou and Liuh Chii Lin, "Fast Array Multiplications over GF (2m) Fields with Multiple Speeds", Tamkang Journal of Science and Engineering, Vol. 7, No 3, 2004 , pp. 139-144.

[11] Junfeng Fan and Ingrid Verbauwhede, "A Digit-Serial Architecture for Inversion and Multiplication in GF(2m)", IEEE Workshop on Signal Processing Systems, 8-10 Oct. 2008, pp. 7-12.

[12] Lejla Batina, Nele Mentens, Sıddıka Berna Ors, Bart Preneel, "Serial Multiplier Architectures over GF(2m) for Elliptic Curve Cryptosystems", 12th IEEE Electro technical Conference, Vol.2 2004, pp. 779-782.

[13] Jeng-Shyang Pan, Chiou-Yng Lee and Pramod Kumar Meher, "Low-Latency Digit-Serial and Digit-Parallel Systolic Multipliers for Large Binary Extension Fields", IEEE Transactions on Circuits and Systems I: Regular Papers, Dec. 2013, pp. 3195-3204.

[14] Nazar A. Saqib, Francisco Rodriguez-Henriquez and Arturo Diaz-Perez, "A Parallel Architecture for Fast Computation of Elliptic Curve Scalar Multiplication over GF (2m)" 18th International Parallel and Distributed Processing Symposium, 26-30 April 2004.

[15] George N. Selimis, Apostolos P. Fournaris, Harris E. Michail, Odysseas Koufopavlou, "Improved throughput bit-serial multiplier for GF(2m) fields", Integration, the VLSI Journal 42, 2009, pp. 217-226.

[16] Che-Wun Chiou, Chiou-Yng Lee and Jim-Min Lin, "Finite Field Polynomial Multiplier with Linear Feedback Shift Register", Tamkang Journal of Science and Engineering, Vol. 10, No. 3, 2007, pp. 253-264.

[17] Chiou-Yng Lee, Che Wun Chiou , Jim-Min Lin, "Low-complexity bit-parallel dual basis multipliers using the modified Booths algorithm", Computers and Electrical Engineering Vol. 31, 2005, pp. 444-459.

[18] Ali Zakerolhosseini, Morteza Nikooghadam, "Low-power and high-speed design of a versatile bit-serial multiplier in finite fields GF (2m)", Integration, the VLSI Journal Vol. 46, 2013, pp. 211-217.

[19] C. Grabbe, M. Bednara, J. Teich, J. von zur Gathen, J. Shokrollahi "FPGA Designs of Parallel High Performance GF(2233) Multipliers" International Symposium on Circuits and Systems, 2003, Vol. 2, pp. 268-271.

[20] Yin Li, Gongliang Chen, Xiao-ning Xie: "Low complexity bit-parallel GF (2m) multiplier for all-one polynomials", IACR Cryptology ePrint Archive 2012: 414 (2012).

[21] Haining Fan, Jiaguang Sun, Ming Gu and Kwok-Yan Lam, "Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithms", IET Information security, Vol. 4, No. 1, 2010, pp. 8-14.

[22] Sameh M. Shohdy, Ashraf B. El-Sisi, and Nabil Ismail, "Hardware Implementation of Efficient Modified Karatsuba Multiplier Used in Elliptic Curves", International Journal of Network Security, Vol. 11, No. 3, Nov. 2010, pp.155-162.

[23] Mohammed Benaissa and Wei Ming Lim, "Design of Flexible GF(2m) Elliptic Curve Cryptography Processors", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 14, No. 6, June 2006, pp. 659-662.

[24] Arash Reyhani-Masoleh, and M. Anwar Hasan, "Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF (2m)", IEEE Transactions on Computers, Vol. 53, No. 8, August 2004, pp. 945-959.

[25] Chiou-Yng Lee, Chin-Chin Chen,Yuan-Ho Chen and Erl-Huei Lu, "Low-Complexity Bit-Parallel Systolic Multipliers over GF(2m)", IEEE International Conference on Systems, Man, and Cybernetics, 2006, pp. 1-6.

[26] Gang Zhou, Harald Michalik, and László Hinsenkamp, "Complexity Analysis and Efficient Implementations of Bit Parallel Finite Field Multipliers Based on Karatsuba-Ofman Algorithm on FPGAs", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 18, No. 7, July 2010, pp. 1057-1066.

[27] Haining Fan and M. Anwar Hasan, "A New Approach to Sub-quadratic Space Complexity Parallel Multipliers for Extended Binary Fields", IEEE Transactions on Computers, Vol. 56, No. 2, February 2007, pp. 224-233.

[28] Miguel Morales-Sandoval, Claudia Feregrino-Uribe, René Cumplido, Ignacio Algredo-Badillo, "An area/performance trade-off analysis of a GF(2m) multiplier architecture for elliptic curve cryptography", Computers and Electrical Engineering, Vol. 35, 2009, pp. 54-58.

[29] Huapeng Wu, "Bit-Parallel Finite Field Multiplier and Square Using Polynomial Basis", IEEE Transactions Computers, Vol. 51, 2002, pp. 750-758.

[30] Lee, C. Y., Lu, E. H. and Lee, J. Y., "Bit-Parallel Systolic Multipliers for GF (2m) Fields Defined by All-One and Equally-Spaced Polynomials," IEEE Transactions Computers, Vol. 50, 2001, pp. 385-393.

[31] Lee, C. Y., "Low Complexity Bit-Parallel Systolic Multiplier Over GF (2m) Using Irreducible Trinomials," IEE Proc. Comput. Digit. Tech., Vol. 150, 2003, pp. 39-42.

[32] Bahram Rashidi, Reza Rezaeian Farashahi, Sayed Masoud Sayedi, "High-speed and Pipelined Finite Field Bit-Parallel Multiplier over GF(2m) for Elliptic Curve Cryptosystems", Proceedings of the 11th International ISC Conference on Information Security and Cryptology (ISCISC), 3-4 Sept. 2014, pp. 15-20.

[33] G. Zhou, L. Li, and H. Michalik, "Area optimization of bit parallel finite field multipliers with fast carry logic on FPGAs", Proceedings of the International Conference on Field Program. Logic and Applications (ICFPL), Sep. 2008, pp. 671-674.

[34] W. N. Chelton and M. Benaissa, "Fast elliptic curve cryptography on FPGA," IEEE Transactions Very Large Scale Integration (VLSI) System, Vol. 16, No. 2, Feb. 2008, pp. 198-205.

[35] F. Rodríguez-Henríquez, N. A. Saqib, and N. Cruz-Cortés, "A fast implementation of multiplicative inversion over GF(2m)", in Proceedings of the International Conference on Inf. Technol.: Coding Computer, 2005, pp. 574-579.

[36] Reza Azarderakhsh, Arash Reyhani-Masoleh, "Low-Complexity Multiplier Architectures for Single and Hybrid-Double Multiplications in Gaussian Normal Bases", IEEE Transactions on Computers, Vol. 62, No. 4, April 2013, pp. 744-757.

[37] Arash Reyhani-Masoleh, "Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases," IEEE Transactions Computers, Vol. 55, No. 1, Jan. 2006, pp. 34-47.

[38] A.H. Namin, H. Wu, and M. Ahmadi, "A Word-Level Finite Field Multiplier Using Normal Basis," IEEE Transactions Computers, Vol. 60, No. 6, June 2010, pp. 890-895.

[39] Arash Reyhani-Masoleh and M.A. Hasan, "A New Construction of Massey-Omura Parallel Multiplier over GF (2m)" IEEE Transactions Computers, Vol. 51, No. 5, May 2002, pp. 511-520.

[40] C. K. Koç and B. Sunar, "An Efficient Optimal Normal Basis Type II Multiplier over GF (2m)" IEEE Transactions Computers, Vol. 50, No. 1, Jan. 2001, pp. 83-87.

[41] Arash Reyhani-Masoleh, M. Anwar Hasan, "Low Complexity Word-Level Sequential Normal Basis Multipliers", IEEE Transactions on Computers, Vol. 54, No. 2, Feb. 2005, pp.98-110.

[42] Arash Reyhani-Masoleh, M. Anwar Hasan, "Efficient Digit-Serial Normal Basis Multipliers over Binary Extension Fields", ACM Transactions on Embedded Computing Systems, Vol. 3, No. 3, August 2004, pp. 575-592.

[43] Jenn-Shyong Horng, I-Chang Jou, Chiou-Yng Lee, "Low-complexity multiplexer-based normal basis multiplier over GF(2m)", Journal of Zhejiang University Science A, 2009 Vol. 10, No.6, pp. 834-842.

[44] Huapeng Wu, "Bit-Parallel Polynomial Basis Multiplier for New Classes of Finite Fields", IEEE Transactions on Computers, Vol. 57, No. 8, August 2008, pp. 1023-1031.

[45] M. Nikooghadam, A. Zakerolhosseini, "Utilization of Pipeline Technique in AOP Based Multipliers with Parallel Inputs", Journal of Signal Processing Systems, Vol. 72, No. 1, pp. 57-62.