Ask Your Question

How to find irreducible polynomial for composite field

asked 2016-07-25 23:29:23 -0500

santoshi gravatar image

the base field is GF(2^3) and extension field is GF(2^3)^2 . how to find second degree irreducible polynomial.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2016-07-27 02:59:51 -0500

B r u n o gravatar image

Your question is a bit unclear to me, but the following may help you:

  • Let us first build $\mathbb F_{2^3}$:

    sage: F.<z> = GF(2^3)
    sage: F
    Finite Field in z of size 2^3
  • Now you can build the polynomial ring $\mathbb F_{2^3}[x]$:

    sage: R.<x> = F[]
    sage: R
    Univariate Polynomial Ring in x over Finite Field in z of size 2^3
  • You can then ask for an irreducible element of degree $2$ in the polynomial ring:

    sage: p = R.irreducible_element(2)
    sage: p
    x^2 + x + z + 1
  • Then you can ask for the extension of $\mathbb F_{2^3}$ using p (with two possible methods), though as you can notice, Sage unfortunately does not know that this is a field:

    sage: K1 = R.quotient_ring(p, 'a')
    sage: K2 = F.extension(p, 'a')
    sage: K1
    Univariate Quotient Polynomial Ring in a over Finite Field in z of size 2^3 with modulus x^2 + x + z + 1
    sage: K2
    Univariate Quotient Polynomial Ring in a over Finite Field in z of size 2^3 with modulus a^2 + a + z + 1
  • Yet, you can ask whether these are fields explicitely:

    sage: K1.is_field()
    sage: K2.is_field()
  • But not that these fields that you construct are not the same (for Sage!) as $\mathbb F_{2^6}$:

    sage: G = GF(2^6)
    sage: K1.base_ring(), K1.modulus()
    (Finite Field in z of size 2^3, x^2 + x + z + 1)
    sage: G.base_ring(), G.modulus()
    (Finite Field of size 2, x^6 + x^4 + x^3 + x + 1)
  • A final note: It would be great if Sage were able to consider tower of extensions for finite fields, but it is not the case. All finite fields are defined over their prime field using an irreducible modulus. If I understand correctly, there has been some work on this by De Feo et al. that you can find on github.

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


Asked: 2016-07-25 23:29:23 -0500

Seen: 168 times

Last updated: Jul 27 '16