Estimating the number of roots of trinomials over finite fields

详细信息    查看全文

• 作者：Zander Kelley¹ ; ^{zander_k@tamu.edu" class="auth_mail" title="E-mail the corresponding author} ; Sean W. Owen¹
• 关键词：Finite field ; Sparse polynomial ; Trinomial ; Poisson distribution ; Chebotarev density
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：March-April 2017
• 年：2017
• 卷：79
• 期：part_P1
• 页码：108-118
• 全文大小：488 K

文摘

We show that univariate trinomials xⁿ+ax^s+b∈F_q[x]$x^n+a{x}^s+b\in {\mathbb{F}}_q[x]$ can have at most $\delta \lfloor \frac{1}{2}+\sqrt{\frac{q-1}{\delta }}\rfloor$ distinct roots in F_q${\mathbb{F}}_q$, where δ=gcd⁡(n,s,q−1)$\delta =\gcd (n,s,q-1)$. We also derive explicit trinomials having $\sqrt{q}$ roots in F_q${\mathbb{F}}_q$ when q   is square and δ=1$\delta =1$, thus showing that our bound is tight for an infinite family of finite fields and trinomials. Furthermore, we present the results of a large-scale computation which suggest that an O(δlog⁡q)$O(\delta \log q)$ upper bound may be possible for the special case where q is prime. Finally, we give a conjecture (along with some accompanying computational and theoretical support) that, if true, would imply such a bound.