Enumerating all the Irreducible Polynomials over Finite Field

2016/02/16 by Bshouty, Nader H., Diab, Nuha, Kawar, Shada R. +1
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1602.05032

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 where N=n² is the size of the output. 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.

Related

• Fast construction of irreducible polynomials over finite fields
• On the Complexity of Exact Counting of Dynamically Irreducible\n Polynomials
• An algorithm for determining the irreducible polynomials over finite fields
• Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
• Polynomial evaluation over finite fields: new algorithms and complexity\n bounds