On the complexity of exact counting of dynamically irreducible polynomials (Q2284970)

Let \(\mathbb{F}_q\) be a finite field having \(q\) elements. A polynomial \(f\in \mathbb{F}_q[X]\) is said to be stable or dynamically irreducible if the \(n\)-th iterate \(f^{(n)}(X)=f\big(f^{(n-1)}(X)\big)\), where \(f^{(0)}(X)=X\), is irreducible over \(\mathbb{F}_q\) for each \(n\ge 1\). A set \(\{f_i(X)\in\mathbb{F}_q[X]:1\le i\le r, \deg(f_i)\ge1\}\) is called dynamically irreducible if all the iterates \(f_{i_1}\circ\cdots\circ f_{i_n}\) are irreducible over \(\mathbb{F}_q\), where \(\{i_1, \ldots, i_n\}\subseteq \{1,\ldots,r\}\). Let \(\mathscr{DI}_q(r)\) denote the set of \(r\) arbitrary pairwise distinct dynamically irreducible quadratic polynomials over \(\mathbb{F}_q\) with the cardinality \(\#\mathscr{DI}_q(r)=\mathsf{DI}_q(r)\) for \(r\ge1\). In this paper, authors study the construction of the set \(\mathscr{DI}_q(r)\) and find its cardinality \(\mathsf{DI}_q(r)\). They present an algorithm which computes all sets of \(r\) pairwise distinct quadratic polynomials which are dynamically irreducible over \(\mathbb{F}_q\) and estimate the time complexity of the algorithm.