Sequential Type-I Optimal Normal Basis Multiplier and Multiplicative Inverse in GF(2m)

Che Wun Chiou This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Chiou-Yng Lee² and Yun-Chi Yeh³

¹Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C.
²Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taoyuan, Taiwan 333, R.O.C.
³Department of Electronic Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C.

REFERENCES

1. [1] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977.
2. [2] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press, 1994.
3. [3] R. E. Blahut, Fast algorithms for digital signal processing, Reading, Mass.: Addison-Wesley, 1985.
4. [4] I. S. Reed and T. K. Truong, The use of finite fields to compute convolutions, IEEE Trans. Information Theory, Vol.IT-21, No.2, pp.208-213, March 1975.
5. [5] B. Benjauthrit and I. S. Reed, “Galois switching functions and their applications,” IEEE Trans. Computers, Vol. C-25, pp.78-86, Jan. 1976.
6. [6] C. C. Wang and D. Pei, “A VLSI design for computing exponentiation in GF(2^m) and its application to generate pseudorandom number sequences,” IEEE Trans. Computers, Vol.39, No.2, pp.258-262, Feb.1990.
7. [7] T. C. Bartee and D. J. Schneider, “Computation with finite fields,” Information and Computing, Vol.6, pp.79-98, Mar. 1963.
8. [8] E. D. Mastrovito, “VLSI architectures for multiplication over finite field GF(2^m),” Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int’l Conf., AAECC-6, T. Mora, ed., Rome, pp.297-309, July 1988.
9. [9] E. D. Mastrovito, “VLSI architectures for computations in Galois fields,” PhD thesis, Linköping Univ., Dept. of Electrical Eng., Linköping, Sweden, 1991.
10. [10] Ç. K. Koç and B. Sunar, “Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields,” IEEE Trans. Computers, Vol.47, No.3, pp.353-356, March 1998.
11. [11] C. Y. Lee, “Low complexity bit-parallel systolic multiplier over GF(2^m) using irreducible trinomials,” IEE Proc.-Comput. Digit. Tech., Vol.150, No.1, pp.39-42, Jan. 2003.
12. [12] T. Itoh and S. Tsujii, “Structure of parallel multipliers for a class of fields GF(2^m)”, Information and Computation, Vol. 83, pp.21-40, 1989.
13. [13] M. A. Hasan, M. Wang, V. K. Bhargava, “Modular construction of low complexity parallel multipliers for a class of finite fields GF(2^m),” IEEE Trans. Computers, Vol.41, No.8, pp.962-971, August 1992.
14. [14] C. Y. Lee, E. H. Lu, and J. Y. Lee, “Bit-parallel systolic multipliers for GF(2^m) fields defined by all-one and equally-spaced polynomials,” IEEE Trans. Computers, Vol.50, No.5, pp.385-393, May 2001.
15. [15] C. Paar, “A new architecture for a parallel finite field multiplier with low complexity based on composite fields,” IEEE Trans. Computers, Vol.45, No.7, pp.856-861, July 1996.
16. [16] C. Paar, P. Fleischmann, and P. Roelse, “Efficient multiplier architectures for Galois Fields GF(2⁴ⁿ)”, IEEE Trans. Computers, Vol.47, No.2, pp.162-170, Feb. 1998.
17. [17] C.W. Chiou, L.C. Lin, F.H. Chou, and S.F. Shu, “Low complexity finite field multiplier using irreducible trinomials,” IEE Electronics Letters, Vol.39, No.24, pp. 1709-1711, Nov. 2003.
18. [18] P. Kitsos, G. Theodoridis, and O. Koufopavlou, “An efficient reconfigurable multiplier architecture for Galois field GF(2^m),” Microelectronics Journal, Vol.34, No.10, pp.975-980, Oct. 2003.
19. [19] E. R. Berlekamp, “Bit-serial Reed-Solomon encoders”, IEEE Trans. Information Theory, Vol.IT-28, pp.869-874, 1982.
20. [20] H. Wu, M. A. Hasan, and I. F. Blake, “New low-complexity bit-parallel finite field multipliers using weakly dual bases,” IEEE Trans. Computers, Vol.47, No.11, pp.1223-1234, November 1998.
21. [21] H. Wu and M. A. Hasan, “Low complexity bit-parallel multipliers for a class of finite fields,” IEEE Trans. Computers, Vol.47, No.8, pp.883-887, Aug. 1998.
22. [22] C.Y. Lee and C.W. Chiou, J.M. Lin, “Low-Complexity Bit-Parallel Dual Basis Multipliers Using the Modified Booth’s Algorithm,” Computers & Electrical Engineering, Vol.31, No.7, pp.444-459, Oct. 2005.
23. [23] J. L. Massey and J. K. Omura, “Computational method and apparatus for finite field arithmetic,” U.S. Patent Number 4,587,627, May 1986.
24. [24] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura, , and I. S. Reed, “VLSI architectures for computing multiplications and inverses in GF(2^m),” IEEE Trans. Computers, Vol.C-34, No.8, pp.709-717, Aug. 1985.
25. [25] A. Reyhani-Masoleh and M. A. Hasan, “A new construction of Massey-Omura parallel multiplier over GF(2^m)”, IEEE Trans. Computers, Vol.51, No.5, pp.511-520, May 2002.
26. [26] A. Reyhani-Masoleh and M. A. Hasan, “Low complexity sequential normal basis multipliers over GF(2^m),” Proc. 16^th IEEE Symposium on Computer Arithmetic, Vol.16, pp.188-195, 2003.
27. [27] A. Reyhani-Masoleh and M.A. Hasan, “Fast normal basis multiplication using general purpose processors,” IEEE Trans. Computers, Vol.52, No.11, pp.1379-1390, Nov. 2003.
28. [28] A. Reyhani-Masoleh, “Efficient algorithms and architectures for field multiplication using Gaussian normal bases,” IEEE Trans. Computers, Vol.55, No.1, pp.34-47, Jan. 2006.
29. [29] A. Reyhani-Masoleh and M. A. Hasan, “Low complexity word-level sequential normal basis multipliers,” IEEE Trans. Computers, Vol.54, No.2, pp.98-110, Feb. 2005.
30. [30] G.B. Agnew, R.C. Mullin, I.M. Onyszchuk, and S.A. Vanstone, “An implementation for a fast public-key cryptosystem,” Journal of Cryptology, Vol.3, pp.63-79, 1991.
31. [31] C.Y. Lee and C.W. Chiou, “Efficient Design of Low-Complexity Bit-Parallel Systolic Hankel Multipliers To Implement multiplication in Normal and Dual Bases of GF(2^m),” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, Vol.E88-A, No.11, pp.3169-3179, Nov. 2005.
32. [32] C.W. Chiou and C.Y. Lee, “Multiplexer-Based Double-Exponentiation for Normal Basis of GF (2^m),” Computers & Security, Vol.24, No.1, pp.83-86, 2005.
33. [33] M.A. Hasan, M.Z. Wang, and V.K. Bhargava, “A modified Massey-Omura parallel multiplier for a class of finite fields,” IEEE Trans. Computers, Vol.42, No.10, pp.1278-1280, Oct. 1993.
34. [34] Applications of Finite Fields, A. J. Menezes, ed., Boston: Kluwer Academic, 1993.
35. [35] R.J. Baker, H.W. Li, and D.E. Boyce, CMOS-Circuit, Design, Layout, and Simulation, IEEE Press, New York, 1998.
36. [36] S.M. Kang and Y. Leblebici, CMOS Digital Integrated Circuits-Analysis and Design, McGraw-Hill, 1999.
37. [37] http://www.st.com/stonline/books/pdf/docs/2006.pdf
38. [38] http://www.st.com/stonline/books/pdf/docs/1885.pdf
39. [39] http://www.st.com/stonline/products/literature/ds/1937/m74hc279.pdf
40. [40] A. Menezes, P. C. Van Oorschot, and S. A. Vanstone, Handbook of applied cryptology, CRC Press, New York, 1997.
41. [41] Y.T. Horng and S.W. Wei, “Fast inverters and dividers for finite field GF(2^m),” Proc. of 1994 IEE Asia-Pacific Conference on Circuits and Systems, Taiwan, pp.206-211, 5-8 Dec. 1994.