Polynomials over finite fields with large images

ABSTRACT

A polynomial ƒ &egr; Fq[&khgr;], 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms