= Polynomial sieve
A polynomial sieve enumerates <irreducible polynomials> by marking <polynomials> divisible by smaller <irreducible polynomials>, analogously to a <number-theoretic sieve>. Over a <finite field> $\mathbb F_q$, there are only $q^d$ <monic polynomials> of each <polynomial degree> $d$, so one can sieve all <monic polynomials> through a prescribed degree $N$.
Process <monic polynomials> in increasing <polynomial degree>. Each unmarked nonconstant <polynomial> is irreducible; mark its <monic polynomial> multiples through degree $N$. Every reducible <polynomial> of degree at most $N$ has an <irreducible polynomial> factor of degree at most $N/2$, so these factors suffice. For example, over the <field with two elements>, the degree-one factors $X$ and $X+1$ mark $X^2$, $X^2+X$ and $X^2+1=(X+1)^2$. The remaining monic quadratic $X^2+X+1$ is irreducible. This gives small defining <polynomials> for constructing <finite fields> as <quotient rings>.
Back to article page