On coefficients of powers of polynomials and their compositions over finite fields

preprint2015arXivOpen access

Abstract

For any given polynomial ff over the finite field Fq\mathbb{F}_q with degree at most q−1q-1, we associate it with a q×qq\times q matrix A(f)=(aik)A(f)=(a_{ik}) consisting of coefficients of its powers (f(x))k=∑i=0q−1aikxi(f(x))^k=\sum_{i=0}^{q-1}a_{ik} x^i modulo xq−xx^q -x for k=0,1,…,q−1k=0,1,\ldots,q-1. This matrix has some interesting properties such as A(g∘f)=A(f)A(g)A(g\circ f)=A(f)A(g) where (g∘f)(x)=g(f(x))(g\circ f)(x) = g(f(x)) is the composition of the polynomial gg with the polynomial ff. In particular, A(f(k))=(A(f))kA(f^{(k)})=(A(f))^k for any kk-th composition f(k)f^{(k)} of ff with k≥0k \geq 0. As a consequence, we prove that the rank of A(f)A(f) gives the cardinality of the value set of ff. Moreover, if ff is a permutation polynomial then the matrix associated with its inverse A(f(−1))=A(f)−1=PA(f)PA(f^{(-1)})=A(f)^{-1}=PA(f)P where PP is an antidiagonal permutation matrix. As an application, we study the period of a nonlinear congruential pseduorandom sequence aˉ={a0,a1,a2,...}\bar{a} = \{a_0, a_1, a_2, ... \} generated by an=f(n)(a0)a_n = f^{(n)}(a_0) with initial value a0a_0, in terms of the order of the associated matrix. Finally we show that A(f)A(f) is diagonalizable in some extension field of Fq\mathbb{F}_q when ff is a permutation polynomial over Fq\mathbb{F}_q.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.