Revista Matemática Iberoamericana


Full-Text PDF (189 KB) | Metadata | Table of Contents | RMI summary
Volume 35, Issue 3, 2019, pp. 847–855
DOI: 10.4171/rmi/1072

Published online: 2019-04-15

Irreducible polynomials over finite fields produced by composition of quadratics

David Rodney Heath-Brown[1] and Giacomo Micheli[2]

(1) Oxford University, UK
(2) Oxford University, UK

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, when $\#S > 1$, we give an algorithm to determine whether all the elements in $C$ are irreducible, using only $O( \#S(\log q)^3 q^{1/2} )$ operations.

Keywords: Finite fields, irreducible polynomials, dynamical systems

Heath-Brown David Rodney, Micheli Giacomo: Irreducible polynomials over finite fields produced by composition of quadratics. Rev. Mat. Iberoam. 35 (2019), 847-855. doi: 10.4171/rmi/1072