# Is there any algorithm that produces irreducible polynomials over $\mathbb{F}_2$?

Is there any (fast) algorithm that produces irreducible polynomials over $\mathbb{F}_2$?

EDIT: I look up for a irreducible polynomial generator, that is different from decider algorithm for irreducibility.

EDIT2: By Input $n \in \mathbb{N}$ to the algorithm $A$ we expect $n$ irreducible polynomials over $\mathbb{F}_2$. I need that $A$ always returns same result by a specific input $n$ (I don't want random irr. polynomials generator).

• Here: $x$ is an irreducible polynomial over $\mathbb{F}_2$. Please review How to Ask. Give more detail as to what is actually to be done by "any (fast) algorithm". Nov 14, 2015 at 19:03
• There are some families of polynomials over $\Bbb{F}_2$ that are known to consist entirely of irreducible ones. See this thread. In general producing them is about as difficult (or easy) as producing prime numbers. Pavel Yudaev describes below the equivalent of the sieve of Eratosthenes. I'm not sure that this is what you wanted. May be you need to build a database of such polynomials? If you use these tricks you will often (but not always) get six irreducible polynomials for the price of one. Nov 14, 2015 at 21:35
• Oh. And if you want irreducible polynomials of a certain degree $m$, you can try Berlekamp on $x^{2^m}+x$ :-) Nov 14, 2015 at 21:42
• @JyrkiLahtonen Thanks for links. Nov 15, 2015 at 5:03

1) $x^2 + x + 1$ is the only irreducible poly of $deg=2$
2) $x^3 + x + 1$ and $x^3 + x^2 + 1$ - all irreducible of $deg=3$
3) for any (next) degree $k$, pick a poly $f$ of degree $k$, try to divide it by $x$, $x+1$ and all irreducible of degree up to $[k/2]$. If no divisor is found, $f$ is irreducible.
4) For your algo to produce the same result, return the first $n$ irreducible polys (of low degrees).
• Computing the minimal polynomial will only help "randomize" a source of polynomials. It doesn't guarantee irreducibility, so we still need either to find an irreducible factor (or test/reject the sample and try again). However we can compute the minimal polynomial of a binary matrix in polynomial time by looking for linear dependence among "flattened rows" that represent the powers $I,A,A^2,\ldots$. If this is of interest, I will elaborate. Nov 15, 2015 at 12:27