Irreducible polynomials over finite fields produced by composition of quadratics (Q2313565)

Summary: 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.