Irreducible polynomials over finite fields produced by composition of quadratics

2017/01/18 by D. R. Heath‐Brown, Heath-Brown, D. R., Giacomo Micheli +1
Computer Science · Engineering · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1701.05031

openalex publication_date 2017/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a set S of quadratic polynomials over a finite field, let C be the (infinite) set of arbitrary compositions of elements in S. In this paper we show that there are examples with arbitrarily large S such that every polynomial in C is irreducible. As a second result, we give an algorithm to determine whether all the elements in C are irreducible, using only O( #S (log q)³ q^1/2 ) operations.

Related

• Irreducible Compositions of Polynomials over Finite Fields
• Irreducibility results for compositions of polynomials in several variables
• An algorithm for determining the irreducible polynomials over finite fields
• Construction of irreducible polynomials through rational transformations
• Number of irreducible polynomials in several variables over finite fields