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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si1.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=c8a647fda00722e0a713ccb2135dfa40" title="Click to view the MathML source">xⁿ+ax^s+b∈F_q[x]class="mathContainer hidden">class="mathCode">$x^n+a{x}^s+b\in {\mathbb{F}}_q[x]$ can have at most class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si2.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=123851bdcb7adab2ddac3ec01e463fac">class="imgLazyJSB inlineImage" height="30" width="84" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0747717116300876-si2.gif">class="mathContainer hidden">class="mathCode">$\delta \lfloor \frac{1}{2}+\sqrt{\frac{q-1}{\delta }}\rfloor$ distinct roots in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si17.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=093fb036c4a1c93572d56ed2613b59d4" title="Click to view the MathML source">F_qclass="mathContainer hidden">class="mathCode">${\mathbb{F}}_q$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si4.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=832f517b99766a04ff068f8ac8c8b651" title="Click to view the MathML source">δ=gcd⁡(n,s,q−1)class="mathContainer hidden">class="mathCode">$\delta =\gcd (n,s,q-1)$. We also derive explicit trinomials having class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si5.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=e2997cf0b577637472ec9142eb3a2130">class="imgLazyJSB inlineImage" height="15" width="22" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0747717116300876-si5.gif">class="mathContainer hidden">class="mathCode">$\sqrt{q}$ roots in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si17.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=093fb036c4a1c93572d56ed2613b59d4" title="Click to view the MathML source">F_qclass="mathContainer hidden">class="mathCode">${\mathbb{F}}_q$ when q   is square and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si6.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=d21d80729b3e4cdb7b638c4a188d3371" title="Click to view the MathML source">δ=1class="mathContainer hidden">class="mathCode">$\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si7.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=76a84985418a8429e9b111a78d62b3c4" title="Click to view the MathML source">O(δlog⁡q)class="mathContainer hidden">class="mathCode">$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.