Galois Field tower field representation

asked 2022-05-17 23:10:22 +0100

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?

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2022-05-18 05:39:52 +0100

slelievre
17684 ●22 ●160 ●349 http://carva.org/samue...

updated 2022-05-18 05:51:26 +0100

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

edit flag offensive delete 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 ( 2022-05-18 13:36:15 +0100 )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)

slelievre ( 2022-05-18 18:12:35 +0100 )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$.

dan_fulea ( 2022-05-18 23:45:38 +0100 )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.

torres ( 2022-05-21 10:08:17 +0100 )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)

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

see more comments

answered 2022-05-18 23:42:11 +0100

dan_fulea
5537 ●5 ●43 ●95

updated 2022-05-18 23:42:59 +0100

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

edit flag offensive delete link

add a comment

Your Answer

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

Add Answer

Galois Field tower field representation

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Galois Field tower field representation edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Galois Field tower field representation