A polynomial sieve enumerates irreducible polynomials by marking polynomials divisible by smaller irreducible polynomials, analogously to a number-theoretic sieve. Over a finite field , there are only monic polynomials of each polynomial degree , so one can sieve all monic polynomials through a prescribed degree .
Process monic polynomials in increasing polynomial degree. Each unmarked nonconstant polynomial is irreducible; mark its monic polynomial multiples through degree . Every reducible polynomial of degree at most has an irreducible polynomial factor of degree at most , so these factors suffice. For example, over the field with two elements, the degree-one factors and mark , and . The remaining monic quadratic is irreducible. This gives small defining polynomials for constructing finite fields as quotient rings.
New to topics? Read the docs here!