On coefficients of powers of polynomials and their compositionsover finite fields

Gary L. Mullen, Amela Muratović-Ribić, Qiang Wang

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationContemporary Developments in Finite Fields and Applications
PublisherWorld Scientific Publishing Co. Pte Ltd
Number of pages12
ISBN (Electronic)9789814719261
ISBN (Print)9789814719254
StatePublished - Aug 1 2016

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'On coefficients of powers of polynomials and their compositionsover finite fields'. Together they form a unique fingerprint.

Cite this