Irreducible polynomials over finite fields produced by composition of quadratics

Author: 

Heath-Brown, D
Micheli, G

Publication Date: 

1 January 2019

Journal: 

REVISTA MATEMATICA IBEROAMERICANA

Last Updated: 

2020-03-25T10:12:24.69+00:00

Issue: 

3

Volume: 

35

DOI: 

10.4171/RMI/1072

page: 

847-855

abstract: 

© European Mathematical Society 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)3q1/2) operations.

Symplectic id: 

1028195

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article