Galois Field tower field representation

torres
31 ●1 ●2 ●6

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)
<ipython-input-7-ca2ad50ca645> in <module>
----> 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?

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2 years ago

slelievre
17799 ●22 ●163 ●352 http://carva.org/samue...

updated 2 years ago

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

link

Comments

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?

torres ( 2 years ago )

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)

slelievre ( 2 years ago )

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

dan_fulea ( 2 years ago )

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.

torres ( 2 years ago )

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)

slelievre ( 2 years ago )

see more comments

answered 2 years ago

dan_fulea
5650 ●5 ●44 ●97

updated 2 years ago

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

link

add a comment