**Che-Wun Chiou This email address is being protected from spambots. You need JavaScript enabled to view it. ^{1}, Chiou-Yng Lee^{2} and Jim-Min Lin^{3} **

^{1}Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C. ^{2}Department of Computer Information and Network Engineering, Lung Hwa University of Science & Technology, Taoyuan, Taiwan 333, R.O.C. ^{3}Department of Information Engineering and Computer Science, Feng Chia University, Taichung, Taiwan 407, R.O.C.

Received:
December 1, 2005

Accepted:
October 2, 2006

Publication Date:
September 1, 2007

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

**ABSTRACT**

We will present an one-dimensional polynomial basis array multiplier for performing multiplications in finite field GF(2^{m}). A linear feedback shift register is employed in our proposed multiplier for reducing space complexity. As compared to other existing two-dimensional polynomial basis multipliers, our proposed linear array multiplier drastically reduces the space complexity from O(m^{2}) to O(m). A new two-dimensional systolic array version of the proposed array multiplier is also included in this paper. The proposed two-dimensional systolic array multiplier saves about 30% of space complexity and 27% of time complexity while comparing with other two-dimensional systolic array multipliers.

Keywords:
Finite Field, Multiplication, Polynomial Basis, Systolic Array, Cryptography

**REFERENCES**

- [1] MacWilliams, F. J. and Sloane, N. J. A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland (1977).
- [2] Lidl, R. and Niederreiter, H., Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press, U.S.A. (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] 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).
- [6] Omura, J. and Massey, J., “Computational Method and Apparatus for Finite Field Arithmetic,” U.S. Patent Number 4,587,627 (1986).
- [7] Wang, C. C., Truong, T. K., Shao, H. M., Deutsch, L. J., Omura, J. K. and Reed, I. S., “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Trans. Computers, Vol. C-34, pp. 709717 (1985).
- [8] 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).
- [9] Berlekamp, E. R., “Bit-Serial Reed-Solomon Encoder,” IEEE Trans. Inform. Theory, Vol. IT-28, pp. 869874 (1982).
- [10] 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).
- [11] Wu, H. and Hasan, M. A., “Low Complexity BitParallel Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 883887 (1998).
- [12] Lee, C. Y., Chiou, C. W. and Lin, J. M., “LowComplexity Bit-Parallel Dual Basis Multipliers Using the Modified Booth’s Algorithm,” Computers & Electrical Engineering, Vol. 31, pp. 444459 (2005).
- [13] 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 Trans. on Fundamentals of Electronics, Communications and Computer Science, Vol. E88-A, pp. 31693179 (2005).
- [14] Bartee, T. C. and Schneider, D. J., “Computation with Finite Fields,” Information and Computing, Vol. 6, pp. 7998 (1963).
- [15] 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).
- [16] Mastrovito, E. D., “VLSI Architectures for Computations in Galois Fields,” Ph.D. thesis, Linköping Univ., Dept. of Electrical Eng., Linköping, Sweden (1991).
- [17] Koç, Ç. K. and Sunar, B., “Low-Complexity BitParallel Canonical and Normal Basis Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 353356 (1998).
- [18] Sunar, B. and Koç, Ç. K., “Mastrovito Multiplier for All Trinomials,” IEEE Trans. Computers, Vol. 48, pp. 522527 (1999).
- [19] Wu, H., “Bit-Parallel Finite Field Multiplier and Square Using Polynomial Basis,” IEEE Trans. Computers, Vol. 51, pp. 750758 (2002).
- [20] 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).
- [21] Wu, H., “Montgomery Multiplier and Squarer for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 51, pp. 521529 (2002).
- [22] 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).
- [23] 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).
- [24] Itoh, T. and Tsujii, S., “Structure of Parallel Multipliers for a Class of Fields GF(2m),” Information and Computation, Vol. 83, pp. 2140 (1989).
- [25] Hasan, M. A., 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).
- [26] 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).
- [27] 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).
- [28] Paar, C., Fleischmann, P. and Roelse, P., “Efficient Multiplier Architectures for Galois Fields GF(24n),” IEEE Trans. Computers, Vol. 47, pp. 162170 (1998).
- [29] Kim, N.-Y., Kim, H.-S. and Yoo, K.-Y., “Computation of AB2 Multiplication in GF(2m) Using Low-Complexity Systolic Architecture,” IEE Proc.-Circuits, Devices and Systems, Vol. 150, pp. 119123 (2003).
- [30] Drolet, G., “A New Representation of Elements of Finite Fields GF(2m) Yielding Small Complexity Arithmetic Circuits,” IEEE Trans. Computers, Vol. 47, pp. 938946 (1998).
- [31] Wang, C.-L. and Lin, J.-L., “Systolic Array Implementation of Multipliers for Finite Fields GF(2m),” IEEE Trans. Circuits and Systems, Vol. 38, pp. 796800 (1991).
- [32] Wei, S.-W., “A Systolic Power-Sum Circuit for GF(2m),” IEEE Trans. Computers, Vol. 43, pp. 226229 (1994).
- [33] Wei, S.-W., “VLSI Architectures for Computing Exponentiations, Multiplicative Inverses, and Divisions in GF(2m),” IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 44, pp. 847855 (1997).
- [34] 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).
- [35] Wang, C. L. and Guo, J. H., “New Systolic Arrays for C+AB2 , Inversion, and Division in GF(2m),” IEEE Trans. Computers, Vol. 49, pp. 11201125 (2000).
- [36] Hsu, I. S., Truong, T. K., Deutsch, L. J. and Reed, I. S., “A Comparison of VLSI Architecture of Finite Field Multipliers Using Dual, Normal, or Standard Bases,” IEEE Trans. Computers, Vol. 37, pp. 735739 (1988).
- [37] Weste, N. and Eshraghian, K., Principles of CMOS VLSI Design: A System Perspective, Reading, Mass.: Addison-Wesley (1985).
- [38] http://www.st.com/stonline/books/pdf/docs/2006.pdf
- [39] http://www.st.com/stonline/books/pdf/docs/1885.pdf
- [40] Http://www.stm.com/stonline/products/literature/ ds/1937/m74hc279.pdf