Estimating the Number Of Roots of Trinomials over Finite Fields

Abstract : We show that univariate trinomials $x^n + ax^s + b \in \mathbb{F}_q[x]$ can have at most $\delta \Big\lfloor \frac{1}{2} +\sqrt{\frac{q-1}{\delta}} \Big\rfloor$ distinct roots in $\mathbb{F}_q$, where $\delta = \gcd(n, s, q - 1)$. We also derive explicit trinomials having $\sqrt{q}$ roots in $\mathbb{F}_q$ when $q$ is square and $\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(\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.
Keywords :
Type de document :
Communication dans un congrès
MEGA'2015 (Special Issue), Jun 2015, Trento, Italy

https://hal.inria.fr/hal-01350784
Contributeur : Alain Monteil <>
Soumis le : lundi 1 août 2016 - 16:57:22
Dernière modification le : mardi 2 août 2016 - 01:01:00

Identifiants

• HAL Id : hal-01350784, version 1
• ARXIV : 1510.01758

Citation

Zander Kelley, Sean Owen. Estimating the Number Of Roots of Trinomials over Finite Fields. MEGA'2015 (Special Issue), Jun 2015, Trento, Italy. 〈hal-01350784〉

Métriques

Consultations de la notice