Home Journals Books For Authors and Reviewers Online Submission News About Us Contact Us
Search
magazinelogo

Journal of Applied Mathematics and Computation

ISSN Print: 2576-0645 Downloads: 145307 Total View: 1793890
Frequency: quarterly ISSN Online: 2576-0653 CODEN: JAMCEZ
Email: jamc@hillpublisher.com
Search articles within this journal Submit an article

Journal Menu

Volumes & Issues

Current Issue

Download PDF

How to cite this paper

3853

TOTAL VIEWS

More Articles

Article Open Access http://dx.doi.org/10.26855/jamc.2022.12.010

Low-Space Complexity Finite Field Multiplier Using Both Dickson and Polynomial Bases

Che Wun Chiou1,*, Cheng-Min Lee2, Yuh-Sien Sun2, Chiou-Yng Lee3, Jim-Min Lin4, Tai-Pao Chuang1

1Department of Computer Science and Information Engineering, Chien Hsin University of Science and Technology, Taoyuan City, Taiwan, China.

2Department of Electronic Engineering, Chien Hsin University of Science and Technology, Taoyuan City, Taiwan, China.

3Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taoyuan City, Taiwan, China.

4Department of Information Engineering and Computer Science, Feng Chia University, Taichung City, Taiwan, China.

*Corresponding author: Che Wun Chiou

Published: January 14,2023

Abstract

Finite field arithmetic is one of the most commonly mathematic operations for cryptography. The finite field arithmetic operations over GF(2m) are largely uti-lized for point multiplication in elliptic curve cryptography. The most important arithmetic operation in GF(2m) is multiplications. Therefore, low-space complexity multipliers over GF(2m) have received significant attention in the hardware implementation of elliptic curve cryptosystems for resource-restricted devices such as smart phones. In finite fields, the implementation of multiplication depends heavily on the choice of basis used to represent field elements, e.g., the polynomial basis (PB), the dual basis (DB), and the normal basis (NB). Each basis has their advantages. Dickson basis is a new one in recent years. In this paper, we derive a low-space complexity multiplier using a double basis that consists of polynomial and Dickson bases. The proposed multiplier employs a linear-feedback shift register to process weight multiplications and has a linear space complexity that is significantly less than that of the recently developed subquadratic space complexity multipliers. The first multiplier which employs both polynomial and Dickson bases will be presented.

References

[1] Miller, V.S. (1986). Use of elliptic curves in cryptography. Proc. of Crypto 85, LNCS 218, Springer, 417-426.

[2] Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48, 203-209.

[3] FIPS PUB 186-2, Digital signature standard (DSS). National Institute of Standards and Technology, Jan. 2000.

[4] Bartee, T.C., Schneider, D. J. (1963). Computation with finite fields. Information and Computing, 6, 79-98.

[5] Mastrovito, E.D. (1988). VLSI architectures for multiplication over finite field GF(2m). Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int’l Conf., AAECC-6, T. Mora, ed., Rome, 297-309.

[6] Itoh, T., Tsujii, S. (1989). Structure of parallel multipliers for a class of fields GF(2m). Information and Computation, 83, 21-40.

[7] Huang, W.-T., Chang, C. H., Chiou, C. W., Tan, S.-Y. (2011). Non-XOR approach for low-cost bit-parallel polynomial basis multiplier over GF(2m). IET Information Security, 5(3), 152-162.

[8] Fan, H., Hasan, M.A. (2007). A new approach to subquadratic space complexity parallel multipliers for extended binary fields. IEEE Trans. Computers, 56(2), 224-233.

[9] Berlekamp, E.R. (1982). Bit-serial reed-solomon encoder. IEEE Trans. Inf. Theory, IT-28, 869-874.

[10] Wu, H., Hasan, M. A., Blake, I. F. (1998). New low-complexity bit-parallel finite field multipliers using weakly dual bases. IEEE Trans. Computers, 47(11), 1223-1234.

[11] Chiou, C.W., Lee, C.-Y., Lin, J.-M., Yeh, Y.-C., Pan, J.-S. (2017). Low-Latency Digit-Serial Dual Basis Multiplier for Lightweight Cryptosystems. IET Information Security, 11(6), 301-311.

[12] Massey, J. L., Omura, J. K. (1986). Computational method and apparatus for finite field arithmetic. U.S. Patent Number 4,587,627.

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

[14] Kwon, S. (2003). A low complexity and a low latency bit parallel systolic multiplier over GF(2m) using an optimal normal basis of type II. Proc. of the 16th IEEE Symposium on Computer Arithmetic, Santiago de Compostela, Spain, 196-202.

[15] Lee, C.-Y., Chiou, C. W. (2012). Scalable Gaussian normal basis multipliers over GF(2m) using Hankel matrix-vector represen-tation. Journal of Signal Processing Systems for Signal Image and Video Technology, 69(2), 197-211.

[16] Chiou, C. W., Sun, Y.-S., Lee, C.-M., Lin, J.-M., Chuang, T.-P., Lee, C.-Y. (2017). Gaussian Normal Basis Multiplier over GF(2m) Using Hybrid Subquadratic and Quadratic TMVP Approach for Elliptic Curve Cryptography. IET Circuits, Devices & Systems, 11(6), 579-588.

[17] Fan, H., Hasan, M.A. (2007). Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases. IEEE Trans. Computers, 56(10), 1435-1437.

[18] Park, S.-M., Hong, D., Seo, C. (2013). Subquadratic space complexity multiplier for GF(2n) using type 4 Gaussian normal bases. ETRI Journal, 35(3), 523-529.

[19] Yang, C.-S., Pan, J.-S., Lee, C.-Y. (2013). Digit-serial GNB multiplier based on TMVP approach over GF(2m). Proc. of 2013 Second International Conference on Robot, Vision and Signal Processing, Kitakyushu, Japan, 123-128.

[20] Dickson, L.E. (1883). The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group. Annals of Mathematics, 11(1/6), 161-183.

[21] Mullin, R.C., Mahalanobis, A. (2007). Dickson bases and finite fields. Technical report, University of Waterloo, Canada.

[22] Hasan, M.A., Negre, C. (2008). Subquadratic space complexity multiplication over binary fields with Dickson polynomial representation. Proc. Second Int’l Workshop Arithmetic of Finite Fields, LNCS 5130, 88-102.

[23] Hasan, M.A., Negre, C. (2011). Low space complexity multiplication over binary fields with Dickson polynomial representation. IEEE Trans. on Computers, 60(4), 602-607.

[24] Hasan, M.A. (1998). Double-basis multiplicative inversion over GF(2m). IEEE Trans. on Computers, 47(9), 960-970.

[25] Pan, J.-S., Azarderakhsh, R., Kermani, M. M., Lee, C.-Y., Lee, W.-Y., Chiou, C.W., Lin, J.-M. (2014). Low-latency digit-serial systolic double basis multiplier over GF(2m) using subquadratic Toeplitz matrix-vector product approach. IEEE Trans. Computers, 63(5), 1169-1181.

[26] Lild, R., Mullen, G. L., Turnwald, G. (1993). Dickson polynomials. Pitman Monograph and Survey in Pure and Applied Mathematics, Longman, London.

[27] Gao, S., Mullen, G. L. (1994). Dickson polynomials and irreducible polynomials over finite fields. Journal of Number Theory, 49, 118-132

[28] NanGate Standard Cell Library [Online]. Available: http://www.si2.org/openeda.si2.org/projects/nangatelib/.

How to cite this paper

Low-Space Complexity Finite Field Multiplier Using Both Dickson and Polynomial Bases

How to cite this paper:  Che Wun Chiou, Cheng-Min Lee, Yuh-Sien Sun, Chiou-Yng Lee, Jim-Min Lin, Tai-Pao Chuang. (2022) Low-Space Complexity Finite Field Multiplier Using Both Dickson and Polynomial Bases. Journal of Applied Mathematics and Computation, 6(4), 482-491.

DOI: http://dx.doi.org/10.26855/jamc.2022.12.010

Home　|　Journals　|　Books　|　For Authors and Reviewers　|　Online Submission　|　Contact Us　|　About Us

Copyright © 2023 Hill Publishing Group Inc. All Rights Reserved.