How to get the irreducible polynomial?

Question

I am struggling with the finite field. It is easy to work out all the irreducible polynomials. polynomials when the order is low say 3,4 over $\mathbb F_2$. But is there an easy way to write out all the irreducible polynomial if the order becomes higher like 6? How to tell which of these polynomials are primitive over $\mathbb F_2$?

Answer 1

Since there are only finitely many polynomials of each degree, the Sieve of Eratosthenes can be used to identify which polynomials are irreducible. Irreducible polynomials of every degree are guaranteed to exist by the existence of a field of order $p^n$ for every prime $p$ and every integer $n \ge 1$.

Answer 2

There are $64 = 2^6$ polynomials over $\mathbf{F}_2$ that have degree $6$: you can count this by seeing that each of the six coefficients in degrees $0$ through $5$ can be either $0$ or $1$ independently.

If $\alpha$ is the root of an irreducible degree $6$ polynomial, then $\mathbf{F}_2(\alpha) = \mathbf{F}_{64}$, because that is the unique degree-6 extension of $\mathbf{F}_2$. We can count irreducible polynomials by counting the number of elements $\alpha \in \mathbf{F}_{64}$ satisfy $\mathbf{F}_2(\alpha) = \mathbf{F}_{64}$. The key is that this condition if true if and only if $\alpha$ does not lie in any of the subfields of $\mathbf{F}_{64}$.

The subfields of $\mathbf{F}_{64}$ are $\mathbf{F}_2$, $\mathbf{F}_4$, and $\mathbf{F}_8$. These have $2$, $4$, and $8$ elements respectively, but they all share the same $2$ elements of $\mathbf{F}_2$, so they add up to $10$ elements in all. (this can be done systematically in general by an inclusion-exclusion counting argument)

Thus, there are 54 elements of $\mathbf{F}_{64}$ that do not lie in a proper subfield. They are organized in Galois orbits -- groups of $6$ elements that are all roots of the same irreducible polynomial. Thus, there are $9$ irreducible polynomials of degree $6$ over $\mathbf{F}_2$.

The multiplicative subgroup of $\mathbf{F}_{64}$ is a cyclic group of order $63$. Therefore, there are $\varphi(63) = 36$ distinct primitive elements. Again, these organize in groups of $6$, and so there should be $6$ primitive polynomials of degree $6$ over $\mathbf{F}_2$.

So, it turns out there aren't really very many things to deal with. If you actually construct a representation of the field $\mathbf{F}_{64}$, you could directly compute the minimal polynomials of various elements, until you find $9$ different irreducible polynomials. If you find one primitive element, you can quickly identify which other elements are primitive, and thus decide which of the polynomials are primitive.