Portal de Periódicos da CAPES

Values of polynomials over finite fields

1991; Cambridge University Press; Volume: 43; Issue: 1 Linguagem: Inglês

10.1017/s0004972700028860

1755-1633

Joachim von zur Gathen,

Cryptography and Data Security

Let q be a prime power, Fq a field with q elements, f ∈ Fq[x] a polynomial of degree n ≥ 1, V(f) = #f(Fq) the number of different values f(α) of f, with α ∈ Fq, and p = q – V(f). It is shown that either ρ = 0 or 4n4 > q or 2pn > q. Hence, if q is "large" and f is not a permutation polynomial, then either n or ρ is "large".