Irreducible polynomials over finite fields produced by composition of quadratics

  • David Rodney Heath-Brown

    Oxford University, UK
  • Giacomo Micheli

    Oxford University, UK
Irreducible polynomials over finite fields produced by composition of quadratics cover
Download PDF

A subscription is required to access this article.

Abstract

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

Cite this article

David Rodney Heath-Brown, Giacomo Micheli, Irreducible polynomials over finite fields produced by composition of quadratics. Rev. Mat. Iberoam. 35 (2019), no. 3, pp. 847–855

DOI 10.4171/RMI/1072