Ask Your Question
1

irreducible polynomial defining the finite field

asked 2018-03-10 18:22:06 +0100

omgggggg gravatar image

updated 2018-03-10 18:23:17 +0100

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 flag offensive close merge delete

3 Answers

Sort by ยป oldest newest most voted
1

answered 2018-03-10 22:35:49 +0100

B r u n o gravatar image

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.

edit flag offensive delete link more
0

answered 2018-03-11 00:28:24 +0100

dan_fulea gravatar image

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.

edit flag offensive delete link more

Comments

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

RWBUMP gravatar imageRWBUMP ( 2022-06-06 17:49:57 +0100 )edit
0

answered 2018-03-10 22:31:20 +0100

vdelecroix gravatar image

updated 2018-03-10 22:33:12 +0100

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
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 4,069 times

Last updated: Mar 11 '18