Polynomials over finite fields with large images
Joachim von zur Gathen · 1990
A polynomial ƒ ε Fq[χ], over a finite field Fq with q elements, is p-large if its image in Fq contains at least q - p elements. This Extended Abstract presents an efficient probabilistic test for this property, using expected time polynomial in deg ƒs, log q, and p.