Ask Your Question

# irreducible polynomial defining the finite field

X = GF(2).polynomial_ring().gen()

F = GF(2^8, name="a", modulus=X^8 + X^6 + X^5 + X + 1)

As example above, the polynomial X^8 + X^6 + X^5 + X + 1 is one of irreducible polynomial defining the finite field GF(2^8).

How can I get all the irreducible polynomial which can define the finite field GF(2^8)?

edit retag close merge delete

## 3 Answers

Sort by ยป oldest newest most voted

What you are looking for is the list of all degree-8 irreducible polynomials over $\mathbb F_2$. There is no built-in function for this, but they can be found very easily if you combine polynomials which iterates over all polynomials of a given degree and is_irreducible that tests irreducibilty.

For instance:

sage: R = GF(2)['x']
sage: for p in R.polynomials(8):
....:     if p.is_irreducible():
....:         print(p)
....:
x^8 + x^4 + x^3 + x + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x + 1
[...]
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1


You can also built the list of all of them:

sage: Irr = [p for p in R.polynomials(8) if p is_irreducible()]
sage: len(Irr)
30


Finally, you can have access to some specific irreducible polynomials using R.irreducible_element(algorithm='...'). Have a look at the documentation of irreducible_element for details here.

more

This is a good party, so let me join it!

R.<x> = GF(2)[]
[ p for p, mul in factor( x^(2^8)-x ) if p.degree() == 8 ]


This works since any element in $\mathbb F_{2^8}$ is fixed by the Frobenius morphism $x\to x^{2^8}$. The field generators are among these elements, we insist that they have the maximal degree eight (of the minimal polynomial over $\mathbb F_2$) to pick the generators among all elements. (All ignored multiplicities mul are equal to one.)

This and the other answers show how versatile is sage, and how it supports thinking and experimenting.

more

## Comments

Minor correction needed in code above, change "if p is_irreducible()]" to if p.is_irreducible()]

( 2022-06-06 17:49:57 +0200 )edit

Do you mean

sage: for coeffs in product(GF(2), repeat=8):
....:     p = GF2x(coeffs + (1,))
....:     if p.is_irreducible():
....:         print(p)
....:
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^5 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x + 1
x^8 + x^7 + x^3 + x + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^4 + x^3 + x + 1
x^8 + x^6 + x^5 + x^4 + x^3 + x + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x + 1


Some explanations:

• A polynomial defines GF(2^8) if and only if it has degree 8 and is irreducible
• the product from itertools allow you to run all through all elements of the Cartesian product GF(2)^8
more

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2018-03-10 18:22:06 +0200

Seen: 3,587 times

Last updated: Mar 11 '18