WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 15, 2016
Enumerating all the Irreducible Polynomials over Finite Field
Authors: , , ,
Abstract: In this paper we give a detailed analysis of deterministic and randomized algorithms that enumerate any number of irreducible polynomials of degree n over a finite field and their roots in the extension field in quasilinear time cost per element. Our algorithm is based on an improved algorithm for enumerating all the Lyndon words of length n in linear delay time and the known reduction of Lyndon words to irreducible polynomials.