Computation of the Complexity of some Recursive Constructed Normal Polynomials


  • Mahmood Alizadeh Islamic Azad University- Ahvaz Branch


Complexity, Irreducible Polynomial, Normal Polynomial


In this paper we give some algorithms for computing the complexity of some normal polynomials constructed by some recurrent methods. Finally some results of our algorithms are given in a table.


S. Abrahamyan, “Some construction of N-polynomial sover finite fields", National Academy of Sciences of Armenia Reports, vol. 111, no. 3, 232-239, 2011.

M. Alizadeh, “Some algorithms for normality testing irreducible polynomials and computing complexity of the normal polynomials over finite fields, Applied Mathematical Sciences, vol. 6, no. 40, 1997-2003, 2012.

S. Gao. “Normal bases over finite fields", Ph. D. Thesis, Waterloo, 1993.

M.K. Kyuregyan, “Iterated construction of irreducible polynomials over finite fields with linearly independent roots", Finite Fields Appl., vol. 10, pp. 323-341, 2004.

M.K. Kyuregyan, "Recursive constructions of N-polynomials over GF (2s)", Discrete Applied Mathematics, vol. 156, pp. 1554-1559, 2008.

R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 1987.

A.J. Menezes, I.F. Blake, X. Gao, R.C. Mullin, S.A. Vanstone and T. Yaghoobian, Applications of finite fields, Kluwer Academic publishers, Boston, Dordrecht, Lancaster, 1993.

H. Meyn, "Explicit N-polynomial of 2-power degree over finite fields", Designs, Codes and Cryptography, vol. 6, pp. 147-158, 1995.

R. Mullin, I. Onyszchuk, S. Vanstone and R. Wilson, “Optimal normal bases in GF(pn)n", Discreate Applied math., vol. 22, 149-161, 1988/1989.

J. Omura and J. Massey, “Computational method and apparatus for finite field arithmatic", U.S. patent 4,586,627, 1986.

I. Onyszchuk, R. Mullin, and S. Vanstone, “Computational method and apparatus for multiplication", U.S. patent 4,745,568, 1988.




How to Cite

Alizadeh, M. . (2021). Computation of the Complexity of some Recursive Constructed Normal Polynomials. Mathematical Problems of Computer Science, 36, 57–62. Retrieved from