# 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?

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)


$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$.

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.

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
sage: y = L16
sage: x, y, x + y, x * y
(a*b + a, b + 1, (a + 1)*b + a + 1, a*b + 1)


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