A Class of Polynomials over Finite Fields

Generalizing the norm and trace mappings for _q^r/ _q, we introduce an interesting class of polynomials over finite fields and study their properties. These polynomials are then used to construct curves over finite fields with many rational points.     

Groups of Permutation Polynomials over Finite Fields

LetFbe a finite field. We apply a result of Thierry Berger (1996,Designs Codes Cryptography,7, 215–221) to determine the structure of all groups of permutations onFgenerated by the permutations induced by the linear polynomials and any power map which induces a permutation onF. This generalizes a result of Leonard Carlitz (1953,Proc. Amer. Math. Soc.,4, 538).     

Taking pth Roots Modulo Polynomials over Finite Fields

In this contribution we show how to find y(x) in the polynomial equation y(x) ^p t(x) mod f(x), where t(x), y(x) and f(x) are polynomials over the field GF(p ^m). The solution of such equations are thought for in many cases, e.g., for p = 2 it is a step in the so-called Patterson Algorithm for decoding binary Goppa codes.     

Enumerating Permutation Polynomials over Finite Fields by Degree

We prove an asymptotic formula for the number of permutations for which the associated permutation polynomial has degree smaller than q−2.     

q-Rook Polynomials and Matrices over Finite Fields

Connections betweenq-rook polynomials and matrices over finite fields are exploited to derive a new statistic for Garsia and Remmel'sq-hit polynomial. Both this new statisticmatand another statistic for theq-hit polynomial ξ recently introduced by Dworkin are shown to induce different multiset Mahonian permutation statistics for any Ferrers board. In addition, for the triangular boards they are shown to generate different families of Euler–Mahonian statistics. For these boards the ξ family includes Denert's statisticden, and gives a new proof of Foata and Zeilberger's Theorem that (exc, den) is equidistributed with (des, maj). Thematfamily appears to be new. A proof is also given that theq-hit polynomials are symmetric and unimodal.     

有限域上一类不可约多项式（英文）

设F_q为q元有限域,其中q是素数p的幂,设n是一个正整数.F_q上一个n次首一多项式f(x)的迹定义为x~(n-1)的系数.令N_q(n,t)表示F_q上迹为t∈F_q的n次首一不可约多项式的个数.基于给定多项式的普通分解与其线性化q-相伴式的符号分解之间的关系,本文给出了一种计算N_q(n,t)的新途径.     

On Characteristic Polynomials of Formal Groups over Finite Fields

Generalizing the results of Serre, Hill and Koch, we give some classification theorems of higher dimensional simple formal groups over finite fields. A relation between endomorphism rings of formal groups over ?_p and characteristic polynomials of their reductions mod p is studied. A condition of existence of formal groups over ?_p with complex multiplication is given. Some formal groups over ?_p are also constructed.     

有限域上一类正形置换多项式

有限域F_(2~n)上,g(x)=b_2~dx~2~d+b_2~(d-1)x~2~(d-1)+…+b_2x~2+b_1x+b_0是2~d次仿射多项式,利用同余类知识和有限域上乘积多项式的次数分布规律,研究了F_(2~n)上形如xg(x)的2~d+1次正形置换多项式的存在性.     

Number of Zeros of Diagonal Polynomials over Finite Fields

Let F be a finite field with q=pf elements, where p is a prime. Let N be the number of solutions (x1,…,xn) of the equation c1xd11+···+cnxdnn=c over the finite fields, where d1∣q−1, ciϵF*(i=1, 2,…,n), and cϵF. In this paper, we prove that if b1 is the least integer such that b1≥∑ni=1 (f/ri) (Di, p−1)/(p−1), then q[b1/f]−1∣N, where ri is the least integer such that di∣pri−1, Didi=pri−1, the (Di, p−1) denotes the greatest common divisor of Di and p−1, [b1/f] denotes the integer part of b1/f. If di=d, then this result is an improvement of the theorem that pb∣N, where b is an integer less than n/d, obtained by J. Ax (1969, Amer. J. Math.86, 255–261) and D. Wan (1988, Proc. AMS103, 1049–1052), under a certain natural restriction on d and n.     

Lower Bounds of Complexity for Polarized Polynomials over Finite Fields

Siberian Mathematical Journal - We obtain an efficient lower bound of complexity for n-ary functions over a finite field of arbitrary order in the class of polarized polynomials. The complexity of...     

有限域上多项式指数和的p-adic估计

设f为有限域上的一个多元多项式.它的次数矩阵Df由出现在f中的次数向量构成.本文利用Df给出了多项式f的指数和的一个p-adic估计,它改进和推广了该方向许多已知的结果.     

有限域上的二次特征与多项式的值集

利用有限域F_q上的二次特征,研究了几类特殊多项式在q≡±1(mod4)时的值集.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

Self-Reciprocal Irreducible Polynomials Over Finite Fields

We classify monic self-reciprocal irreducible polynomials over finite fields in terms of their orders. We also study the weights of these polynomials.     

A Poisson * Negative Binomial Convolution Law for Random Polynomials over Finite Fields

Let F _q[X] denote a polynomial ring over a finite field F _q with q elements. Let 𝒫_n be the set of monic polynomials over F _q of degree n. Assuming that each of the qⁿ possible monic polynomials in 𝒫_n is equally likely, we give a complete characterization of the limiting behavior of P(Ω_n=m) as n→∞ by a uniform asymptotic formula valid for m≥1 and n−m→∞, where Ω_n represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in 𝒫_n. The distribution of Ω_n is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q⁻¹. Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P(Ω_n=m) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Rényi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17–47, 1998