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.

Articles by others on the same topic (0)

There are currently no matching articles.