Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields

Issue title: Hardest Boolean Functions and O.B. Lupanov

Article type: Research Article

Authors: Gashkov, Sergej B. | Gashkov, Igor B.

Affiliations: Department of Mechanics and Mathematics, Moscow State University, Vorobiovy Gory, Moscow, Russia. gashkov@lsili.ru | Faculty of Technology and Science, Department of Mathematics, Karlstads Universitet, Karlstad, Sweden. Igor.Gachkov@kau.se

Note: [] The work was supported by grants RFFI 05–01–00994, Sci. Sch—5400.2006.1 Address for correspondence: Department of Mechanics and Mathematics, Moscow State University, Vorobiovy Gory, Moscow, Russia

Note: [] The work was supported by grant of the Royal Sweden Academy of Sciences

Abstract: We prove some improvements for well-known upper bound of complexity of testing irreducibility of polynomials over finite fields. Also the fast modification of well-known probabilistic algorithm finding a normal bases in special finite fields is presented.

Keywords: Finite fields, irreducible polynomials, normal bases, addition chains

DOI: 10.3233/FI-2010-346

Journal: Fundamenta Informaticae, vol. 104, no. 3, pp. 227-238, 2010