**Che-Wun Chiou ^{1} and Huey-Lin Jeng^{2 }**

^{1}Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C. ^{2}Information Planning Division, Information Technology Development Department, Hua Nan Commercial Bank, LTD, Taipei, Taiwan 100, R.O.C.

Received:
March 11, 2007

Accepted:
August 2, 2007

Publication Date:
June 1, 2008

Download Citation:
||https://doi.org/10.6180/jase.2008.11.2.13

**ABSTRACT**

Fast multiplication in a finite field GF(2^{m}) is a basis step in communications engineering applications, such as error-correcting codes or cryptograph algorithms. A new parallel algorithm on the polynomial basis bit-parallel multiplier is presented. This new parallel algorithm saves about 25% execution time while comparing with the conventional algorithms. The hardware version for the proposed parallel algorithm is also invented. The new hardware structure requires only the space complexity of O(m) while existing multipliers need the space complexity of O(m^{2} ). The time complexity of the proposed multiplier takes only about half of the time complexity of the existing Lee’s multiplier.

Keywords:
Cryptography, Finite Field Arithmetic, Parallel Algorithm, Multiplication, Array Multiplier

**REFERENCES**

- [1] Macwilliams, P. J. and Sloane, N. J. A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland (1978).
- [2] Lidl., R. and Niederreiter, H., Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press (1994).
- [3] Blahut, R. E., Fast Algorithms for Digital Signal Processing, Reading, Mass.: Addison-Wesley (1985).
- [4] Reed, I. S. and Truong, T. K., “The Use of Finite Fields to Compute Convolutions,” IEEE Trans. Information Theory, Vol. IT-21, pp. 208213 (1975).
- [5] Benjauthrit, B. and Reed, I. S., “Galois Switching Functions and Their Applications,” IEEE Trans. Computers, Vol. C-25, pp. 7886 (1976).
- [6] Wang, C. C. and Pei, D., “A VLSI Design for Computing Exponentiation in GF(2m) and its Application to Generate Pseudorandom Number Sequences,” IEEE Trans. Computers, Vol. 39, pp. 258262 (1990).
- [7] Massey, J. L. and Omura, J. K., “Computational Method and Apparatus for Finite Field Arithmetic,” U.S. Patent Number 4,587,627, May (1986).
- [8] Wang, C. C. et al., “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Trans. Computers, Vol. C-34, pp. 709717 (1985).
- [9] Reyhani-Masoleh, A. and Hasan, M. A., “A New Construction of Massey-Omura Parallel Multiplier over GF(2m),” IEEE Trans. Computers, Vol. 51, pp. 511 520 (2002).
- [10] Lee, C. Y. and Chiou, C. W., “Efficient Design of Low-Complexity Bit-Parallel Systolic Hankel Multipliers to Implement Multiplication in Normal and Dual Bases of GF(2m),” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, Vol. E88-A, pp. 31693179 (2005).
- [11] Chiou, C. W. and Lee, C. Y., “Multiplexer-Based Double-Exponentiation for Normal Basis of GF (2m),” Computers & Security, Vol. 24, pp. 8386 (2005).
- [12] Lee, C. Y., Chen, Y. H., Chiou, C. W. and Lin, J. M., “Unified Parallel Systolic Multipliers over GF(2m),” Journal of Computer Science and Technology, Vol. 22, pp. 2838 (2007).
- [13] Berlekamp, E. R., “Bit-Serial Reed-Solomon Encoders,” IEEE Trans. Information Theory, Vol. IT-28, pp. 869874 (1982).
- [14] Wu, H., Hasan, M. A. and Blake, I. F., “New LowComplexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases,” IEEE Trans. Computers, Vol. 47, pp. 12231234 (1998).
- [15] Wu, H. and Hasan, M. A., “Low Complexity Bit-Parallel Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 883887 (1998).
- [16] Bartee, T. C. and Schneider, D. J., “Computation with Finite Fields,” Information and Computing, Vol. 6, pp. 7998 (1963).
- [17] Laws, B. A. J. and Rushforth, C. K., “A Cellular-Array Multiplier for GF(2m),” IEEE Trans. Computers, Vol. C-20, pp. 15731578 (1971).
- [18] Yeh, C. S., Reed, I. S. and Truong, T. K., “Systolic Multipliers for Finite Fields GF(2m),” IEEE Trans. Computers, Vol. C-33, pp. 357360 (1984).
- [19] Mastrovito, E. D., “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, pp. 297309 (1988).
- [20] Mastrovito, E. D., “VLSI Architectures for Computations in Galois Fields,” PhD thesis, Linkoping Univ., Dept. of Electrical Eng., Linkoping, Sweden (1991).
- [21] Koç, Ç. K. and Sunar, B., “Low-Complexity Bit-Parallel Canonical and Normal Basis Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 353356 (1998).
- [22] Sunar, B. and Koç, Ç. K., “Mastrovito Multiplier for All Trinomials,” IEEE Trans. Computers, Vol. 48, pp. 522527 (1999).
- [23] Elia, M., Leone, M. and Visentin, C., “Low Complexity Bit-Parallel Multipliers for GF(2m) with Generator Polynomial xm+xk +1,” Electronics Letters, Vol. 35, pp. 551552 (1999).
- [24] Wu, H., “Bit-Parallel Finite Field Multiplier and Square Using Polynomial Basis,” IEEE Trans. Computers, Vol. 51, pp. 750758 (2002).
- [25] Lee, C. Y., “Low Complexity Bit-Parallel Systolic Multiplier Over GF(2m) Using Irreducible Trinomials,” IEE Proc.-Comput. Digit. Tech., Vol. 150, pp. 3942 (2003).
- [26] Chiou, C. W., Lin, L. C., Chou, F. H. and Shu, S. F., “Low Complexity Finite Field Multiplier Using Irreducible Trinomials,” IEE Electronics Letters, Vol. 39, pp. 17091711 (2003).
- [27] Itoh, T. and Tsujii, S., “Structure of Parallel Multipliers for a Class of Fields GF(2m),” Information and Computation, Vol. 83, pp. 2140 (1989).
- [28] 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 Trans. Computers, Vol. 50, pp. 385393 (2001).
- [29] Hasan, M., Wang, M. and Bhargava, V. K., “Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields GF(2m),” IEEE Trans. Computers, Vol. 41, pp. 962971 (1992).
- [30] Paar, C., “A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields,” IEEE Trans. Computers, Vol. 45, pp. 856861 (1996).
- [31] Paar, C., Fleischmann, P. and Roelse, P., “Efficient Multiplier Architectures for Galois Fields GF(24n),” IEEE Trans. Computers, Vol. 47, pp. 162170 (1998).
- [32] Chiou, C. W., Lee, C. Y. and Lin, J. M., “Efficient Systolic Arrays for Power-Sum, Inversion, and Division in GF(2m),” International Journal of Computer Sciences and Engineering Systems, Vol. 1, pp. 2741 (2007).
- [33] Lee, C. Y., Lin, J. M. and Chiou, C. W., “Scalable and Systolic Architecture for Computing Double Exponentiation Over GF(2m),” Acta Applicandae Mathematicae, Vol. 93, pp. 161178 (2006).
- [34] Lee, C. Y., Chiou, C. W., Deng, A. W. and Lin, J. M., “Low-Complexity Bit-Parallel Systolic Architectures for Computing A(x)B2 (x) Over GF(2m),” IEE Proceedings-Circuits, Devices and Systems, Vol. 153, pp. 399406 (2006).
- [35] Lee, C. Y., Chen, Y. H., Chiou, C. W. and Lin, J. M., “Unified Parallel Systolic Multipliers over GF(2m),” Journal of Computer Science and Technology, Vol. 22, pp. 2838 (2007).