Full Text:   <2138>

CLC number: TP309

On-line Access: 

Received: 2008-05-26

Revision Accepted: 2008-11-18

Crosschecked: 2009-04-29

Cited: 4

Clicked: 4950

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2009 Vol.10 No.6 P.834-842


Low-complexity multiplexer-based normal basis multiplier over GF(2m)

Author(s):  Jenn-Shyong HORNG, I-Chang JOU, Chiou-Yng LEE

Affiliation(s):  Institute of Engineering Science and Technology, National Kaohsiung First University of Science and Technology, Taiwan 811, Kaohsiung County; more

Corresponding email(s):   shyong1@cht.com.tw

Key Words:  Finite field multiplication, Normal basis, Gaussian normal basis, Elliptic curve cryptosystem

Jenn-Shyong HORNG, I-Chang JOU, Chiou-Yng LEE. Low-complexity multiplexer-based normal basis multiplier over GF(2m)[J]. Journal of Zhejiang University Science A, 2009, 10(6): 834-842.

@article{title="Low-complexity multiplexer-based normal basis multiplier over GF(2m)",
author="Jenn-Shyong HORNG, I-Chang JOU, Chiou-Yng LEE",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Low-complexity multiplexer-based normal basis multiplier over GF(2m)
%A Jenn-Shyong HORNG
%A I-Chang JOU
%A Chiou-Yng LEE
%J Journal of Zhejiang University SCIENCE A
%V 10
%N 6
%P 834-842
%@ 1673-565X
%D 2009
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A0820398

T1 - Low-complexity multiplexer-based normal basis multiplier over GF(2m)
A1 - Jenn-Shyong HORNG
A1 - I-Chang JOU
A1 - Chiou-Yng LEE
J0 - Journal of Zhejiang University Science A
VL - 10
IS - 6
SP - 834
EP - 842
%@ 1673-565X
Y1 - 2009
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A0820398

We present a new normal basis multiplication scheme using a multiplexer-based algorithm. In this algorithm, the proposed multiplier processes in parallel and has a multiplexer-based structure that uses MUX and XOR gates instead of AND and XOR gates. We show that our multiplier for type-1 and type-2 normal bases saves about 8% and 16%, respectively, in space complexity as compared to existing normal basis multipliers. Finally, the proposed architecture has regular and modular configurations and is well suited to VLSI implementations.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Agnew, G.B., Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., 1991. An implementation for a fast public-key cryptosystem. J. Cryptol., 3:63-79.

[2] Ash, D.W., Blake, I.F., Vanstone, S.A., 1989. Low complexity normal basis. Discr. Appl. Math., 25(3):191-210.

[3] Byun, G.Y., Kim, H.S., 2003. Low-complexity multiplexer-based multiplier of GF(2m). IEICE Trans. Inf. Syst., E86-D(12):2684-2690.

[4] Elia, M., Leone, M., 2002. On the inherence space complexity of fast parallel multipliers for GF(2m). IEEE Trans. Comput., 51(3):346-351.

[5] Hasan, M.A., Wang, M., Bhargava, V.K., 1992. Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans. Comput., 41(8):962-971.

[6] Hasan, M.A., Wang, M.Z., Bhargava, V.K., 1993. A modified Massey-Omura parallel multiplier for a class of finite fields. IEEE Trans. Comput., 42(10):1278-1280.

[7] IEEE Std. 1363, 2000. IEEE Standard Specifications for Public Key Cryptography. IEEE-SA Standards Board, IEEE/IEE Electronic Library.

[8] Kim, C.H., Kim, Y., Ji, S.Y., Park, I.W., 2006. A New Parallel Multiplier for Type II Optimal Normal Basis. Int. Conf. on Computational Intelligence and Security, 2:1315-1318.

[9] Koc, C.K., Sunar, B., 1998. Low-complexity bit-parallel canonical and normal multipliers for a class of finite fields. IEEE Trans. Comput., 47(3):353-356.

[10] Lee, C.Y., Lu, E.H., Lee, J.Y., 2001. Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials. IEEE Trans. Comput., 50(5):385-393.

[11] Lee, C.Y., Chiou, C.W., Lin, J.M., 2005. Low-complexity bit-parallel dual basis multipliers using the modified Booth’s algorithm. Comput. Electr. Eng., 31(7):444-459.

[12] Lee, C.Y., Chiu, Y.H., Chiou, C.W., 2006. New Bit-parallel Systolic Multiplier Over GF(2m) Using the Modified Booth’s Algorithm. IEEE Asia Pacific Conf. on Circuits and Systems, p.610-613.

[13] Lidl, R., Niederreiter, H., 1994. Introduction to Finite Fields and Their Applications. Cambridge University Press, New York.

[14] MacWilliams, F.J., Sloane, N.J.A., 1977. The Theory of Error-correcting Codes. Amsterdam, North-Holland.

[15] Massey, J.L., Omura, J.K., 1986. Computational Method and Apparatus for Finite Field Arithmetic. US Patent, No. 4 587 627.

[16] Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., Wilson, R.M., 1989. Optimal normal basis in GF(pn). Discr. Appl. Math., 22(2):149-161.

[17] Pekmestzi, K.Z., 1999. Multiplexer-based array multipliers. IEEE Trans. Comput., 48(1):15-23.

[18] Reyhani-Masoleh, A., 2006. Efficient algorithms and architectures for field multiplication using Gaussian normal bases. IEEE Trans. Comput., 55(1):34-47.

[19] Reyhani-Masoleh, A., Hasan, M.A., 2002. A new construction of Massey-Omura parallel multiplier over GF(2m). IEEE Trans. Comput., 51(5):511-520.

[20] Reyhani-Masoleh, A., Hasan, M.A., 2003. Fast normal basis multiplication using general purpose processors. IEEE Trans. Comput., 52(11):1379-1390.

[21] Reyhani-Masoleh, A., Hasan, M.A., 2005. Low complexity word-level sequential normal basis multiplier. IEEE Trans. Comput., 54(2):98-110.

[22] Sunar, B., Koc, C.K., 2001. An efficient optimal normal basis type II multiplier. IEEE Trans. Comput., 50(1):83-88.

[23] Wu, H., 1998. Efficient Computations in Finite Fields with Cryptographic Significance. PhD Thesis, Waterloo University, Ontario.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE