Estimating the number of roots of trinomials over finite fields. (March 2017) - Kelley, Zander; Owen, Sean W.
Abstract: We show that univariate trinomials x n + a x s + b ∈ F q [ x ] can have at most δ ⌊ 1 2 + q − 1 δ ⌋ distinct roots in F q, where δ = gcd ⁡ ( n, s, q − 1 ) . We also derive explicit trinomials having q roots in F q when q is square and δ = 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 ) 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.