Irreducible polynomials over finite fields produced by composition of quadratics
David Rodney Heath-Brown, Giacomo Micheli · Revista Matemática Iberoamericana · 2019
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.