On coefficients of polynomials over finite fields |
| |
Authors: | Amela Muratovi?-Ribi? Qiang Wang |
| |
Institution: | aUniversity of Sarajevo, Department of Mathematics, Zmaja od Bosne 33-35, 71000 Sarajevo, Bosnia and Herzegovina;bSchool of Mathematics and Statistics, Carleton University, Ottawa, ON K1S 5B6, Canada |
| |
Abstract: | In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations. |
| |
Keywords: | MSC: 11T06 12Y05 |
本文献已被 ScienceDirect 等数据库收录! |
|