Parallel Algorithm for Polynomial Basis Multiplier in GF(2m) Fields

Che-Wun Chiou  ¹ and Huey-Lin Jeng²

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

REFERENCES

1. [1] Macwilliams, P. J. and Sloane, N. J. A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland (1978).
2. [2] Lidl., R. and Niederreiter, H., Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press (1994).
3. [3] Blahut, R. E., Fast Algorithms for Digital Signal Processing, Reading, Mass.: Addison-Wesley (1985).
4. [4] Reed, I. S. and Truong, T. K., “The Use of Finite Fields to Compute Convolutions,” IEEE Trans. Information Theory, Vol. IT-21, pp. 208
   213 (1975).
5. [5] Benjauthrit, B. and Reed, I. S., “Galois Switching Functions and Their Applications,” IEEE Trans. Computers, Vol. C-25, pp. 78
   86 (1976).
6. [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. 258
   262 (1990).
7. [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. [8] Wang, C. C. et al., “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Trans. Computers, Vol. C-34, pp. 709
   717 (1985).
9. [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. [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. 3169
    3179 (2005).
11. [11] Chiou, C. W. and Lee, C. Y., “Multiplexer-Based Double-Exponentiation for Normal Basis of GF (2m),” Computers & Security, Vol. 24, pp. 83
    86 (2005).
12. [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. 28
    38 (2007).
13. [13] Berlekamp, E. R., “Bit-Serial Reed-Solomon Encoders,” IEEE Trans. Information Theory, Vol. IT-28, pp. 869
    874 (1982).
14. [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. 1223
    1234 (1998).
15. [15] Wu, H. and Hasan, M. A., “Low Complexity Bit-Parallel Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 883
    887 (1998).
16. [16] Bartee, T. C. and Schneider, D. J., “Computation with Finite Fields,” Information and Computing, Vol. 6, pp. 79
    98 (1963).
17. [17] Laws, B. A. J. and Rushforth, C. K., “A Cellular-Array Multiplier for GF(2m),” IEEE Trans. Computers, Vol. C-20, pp. 1573
    1578 (1971).
18. [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. 357
    360 (1984).
19. [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. 297
    309 (1988).
20. [20] Mastrovito, E. D., “VLSI Architectures for Computations in Galois Fields,” PhD thesis, Linkoping Univ., Dept. of Electrical Eng., Linkoping, Sweden (1991).
21. [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. 353
    356 (1998).
22. [22] Sunar, B. and Koç, Ç. K., “Mastrovito Multiplier for All Trinomials,” IEEE Trans. Computers, Vol. 48, pp. 522
    527 (1999).
23. [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. 551
    552 (1999).
24. [24] Wu, H., “Bit-Parallel Finite Field Multiplier and Square Using Polynomial Basis,” IEEE Trans. Computers, Vol. 51, pp. 750
    758 (2002).
25. [25] Lee, C. Y., “Low Complexity Bit-Parallel Systolic Multiplier Over GF(2m) Using Irreducible Trinomials,” IEE Proc.-Comput. Digit. Tech., Vol. 150, pp. 39
    42 (2003).
26. [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. 1709
    1711 (2003).
27. [27] Itoh, T. and Tsujii, S., “Structure of Parallel Multipliers for a Class of Fields GF(2m),” Information and Computation, Vol. 83, pp. 21
    40 (1989).
28. [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. 385
    393 (2001).
29. [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. 962
    971 (1992).
30. [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. 856
    861 (1996).
31. [31] Paar, C., Fleischmann, P. and Roelse, P., “Efficient Multiplier Architectures for Galois Fields GF(24n),” IEEE Trans. Computers, Vol. 47, pp. 162
    170 (1998).
32. [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. 27
    41 (2007).
33. [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. 161
    178 (2006).
34. [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. 399
    406 (2006).
35. [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. 28
    38 (2007).