On coefficients of powers of polynomials and their compositions over finite fields
For any given polynomial f over the finite field Fq with degree at most q-1, we associate it with a q × q matrix A(f) = (aik) consisting of coefficients of its powers (f(x))k= ∫q-1 i=0 aikxi modulo xq-x for k = 0; 1 q-1. This matrix has some interesting properties such as A(gf) = A(f)A(g) where (gf)(x) = g(f(x)) is the composition of the polynomial g with the polynomial f. In particular, A(f(k)) = (A(f))k for any k-th composition f(k) of f with k ≥ 0. As a consequence, we prove that the rank of A(f) gives the cardinality of the value set of f. Moreover, if f is a permutation polynomial then the matrix associated with its inverse A(f(-1)) = A(f)-1 = PA(f)P where P is an antidiagonal permutation matrix. As an application, we study the period of a nonlinear congruential pseduorandom sequence ā = -a0, a1, a2, generated by an = f(n)(a0) with initial value a0, in terms of the order of the associated matrix. Finally we show that A(f) is diagonalizable in some extension field of Fq when f is a permutation polynomial over Fq.
Mullen, G.L. (Gary L.), Muratović-Ribić, A. (Amela), & Wang, Q. (2016). On coefficients of powers of polynomials and their compositions over finite fields. In Contemporary Developments in Finite Fields and Applications (pp. 270–281). doi:10.1142/9789814719261_0016