# Galois Field tower field representation

I'm trying to create some galois field (GF4, GF16 and GF256) using a tower field representation, as described here:

GF(4) := GF(2)[a] / (a^2 + a+ 1)
GF(16) := GF(4)[b] / (b^2 + b + a)
GF(256) := GF(16)[c] / (c^2 + c + a*b)

I've tried doing that using field extensions, but i've been bumping in errors and dead ends so far. For example, i tried doing something like this:

GF2.<a> = GF(2)
GF4.<b> = GF(4, modulus=a^2+a+1)


But of course i'm getting this error, since the modulus simply evaluates to 1:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
----> 1 GF4 = GF(Integer(2)**Integer(2), modulus=a**Integer(2)+a+Integer(1), names=('b',)); (b,) = GF4._first_ngens(1)

~/sage/sage-9.6/local/var/lib/sage/venv-python3.8/lib/python3.8/site-packages/sage/structure/factory.pyx in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2264)()
365             False
366         """
--> 367         key, kwds = self.create_key_and_extra_args(*args, **kwds)
368         version = self.get_version(sage_version)
369         return self.get_object(version, key, kwds)

~/sage/sage-9.6/local/var/lib/sage/venv-python3.8/lib/python3.8/site-packages/sage/rings/finite_rings/finite_field_constructor.py in create_key_and_extra_args(self, order, name, modulus, names, impl, proof, check_irreducible, prefix, repr, elem_cache, **kwds)
651
652                     if modulus.degree() != n:
--> 653                         raise ValueError("the degree of the modulus does not equal the degree of the field")
654                     if check_irreducible and not modulus.is_irreducible():
655                         raise ValueError("finite field modulus must be irreducible but it is not")

ValueError: the degree of the modulus does not equal the degree of the field


Do you have any idea on how to achieve this?

edit retag close merge delete

Sort by ยป oldest newest most voted

The error is in the polynomial used to define the field extension.

It should use a polynomial variable over the base field, not a field element.

One way to define the fields you want might be as follows:

sage: F2 = GF(2)
sage: a = polygen(F2)
sage: F4.<a> = F2.extension(a^2 + a + 1)
sage: b = polygen(F4)
sage: F16.<b> = F4.extension(b^2 + b + a)
sage: c = polygen(F16)
sage: F256.<c> = F16.extension(c^2 + c + a*b)


This gives:

sage: F2
Finite Field of size 2
sage: F4
Finite Field in a of size 2^2
sage: F16
Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^2 with modulus b^2 + b + a
sage: F256
Univariate Quotient Polynomial Ring in c over Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^2 with modulus b^2 + b + a with modulus c^2 + c + a*b

more

It seems to almost work correctly, i get the expected behaviour when summing together elements of such fields, but not when multiplying them... For example, computing the sum of 5 and 15 in gf16 does output 5 correctly, but their product produces 2. Do you have any idea why?

( 2022-05-18 13:36:15 +0200 )edit

Not sure what you mean there.

sage: x = F16(5)
sage: y = F16(15)
sage: x, y, x + y, x*y
(1, 1, 0, 1)

( 2022-05-18 18:12:35 +0200 )edit

$5$ is an element of $\Bbb Z$, seen in any field above, it is $1$ and is an element of the prime field $\Bbb F_2$ inside each of the fields. And $15=5=1$ in $\Bbb F_2$. Additions and multiplications of these elements are $1+1=0$, $1\cdot 1=1$.

( 2022-05-18 23:45:38 +0200 )edit

I should have been clearer, when i speak about numbers i mean their representation in that specific field: one can get each of those using enumerate.

( 2022-05-21 10:08:17 +0200 )edit

Still not sure what you mean.

sage: L16 = F16.list()
sage: L16
[0,
a,
a + 1,
1,
a*b,
a*b + a,
a*b + a + 1,
a*b + 1,
(a + 1)*b,
(a + 1)*b + a,
(a + 1)*b + a + 1,
(a + 1)*b + 1,
b,
b + a,
b + a + 1,
b + 1]
sage: x = L16[5]
sage: y = L16[15]
sage: x, y, x + y, x * y
(a*b + a, b + 1, (a + 1)*b + a + 1, a*b + 1)

( 2022-05-21 15:37:52 +0200 )edit

Same answer as above. I am only introducing the parallel mathematical objects for comparison.

I will define first F2$=\Bbb F_2$, then F4$= \Bbb F_4$ as $\Bbb F_2[X]/(X^2 + X + 1)$, and $a$ is taken to be the class of $X$ w.r.t. the ideal generated by the "modulus" $X^2+X+1$.

F2 = GF(2)
R2.<X> = PolynomialRing(F2)
F4.<a> = GF(4, modulus=X^2 + X + 1)


So X is specifically the transcendent variable of a polynomial ring R2 over $\Bbb F_2$. Now we proceed in the same manner to introduce the ring R4$=\Bbb F_4[Y]$, and then the field F16$=\Bbb F_4[Y]/(Y^2 + Y + a)$. The class of $Y$ modulo $(Y^2 + Y + a)$ will be denoted by $b$.

R4.<Y> = PolynomialRing(F4)
F16.<b> = F4.extension(Y^2 + Y + a)


And finally, F256$=\Bbb F_{16}[Z]/(Z^2+Z+ab)$, and the class of $Z$ is $c$:

R16.<Z> = PolynomialRing(F16)
F256.<c> = F16.extension(Z^2 + Z + a*b)


We ask for the information of the three fields:

print(f'F4 is {F4}')
print(f'F16 is {F16}')
print(f'F256 is {F256}')


Results (manually rearranged):

F4 is Finite Field in a of size 2^2
F16 is Univariate Quotient Polynomial Ring in b
over Finite Field in a of size 2^2 with modulus b^2 + b + a
F256 is Univariate Quotient Polynomial Ring in c
over Univariate Quotient Polynomial Ring in b
over Finite Field in a of size 2^2 with modulus b^2 + b + a with modulus c^2 + c + a*b

more