Symbolic calculations in finite field extension

Hello,

Please consider the following code snippet:

P_GF2.<X> = PolynomialRing(GF(2))
GF23.<x> = P_GF2.quotient_ring(X^3+X+1)

def f(val):
return val**3

This works as expected, when val is something like $1+x+x^2$. What I wanted to do is to calculate the value of $f$, but using a generic element of $GF(2^3)$, e.g. $a_2x^2+a_1x+a_0$. The idea is to have the result expressed in terms of the $a_i$. Is this possible in Sagemath?

I have tried to do it using symbolic variables, but they always belong to the Symbolic Ring, which (as far as I can tell) does not mix with other rings. Because this example is small, I was able to do the computations by hand; the value of having SAGE doing it is of course, to apply it to cases that are infeasible to do without a computer.

Thank you very much in advance.

edit retag close merge delete

Sort by ยป oldest newest most voted

Instead of symbolic variables, you can define the ai as polynomial indeterminates, as follows:

sage: P_GF2.<X,A0,A1,A2> = PolynomialRing(GF(2))
sage: GF23.<x,a0,a1,a2> = P_GF2.quotient_ring(X^3+X+1)
sage: def f(val):
....:       return val**3
sage: f(a0*+a1*x+a2*x)
x*a0^3*a1^3 + a0^3*a1^3 + x*a0^2*a1^2*a2 + a0^2*a1^2*a2 + x*a0*a1*a2^2 + a0*a1*a2^2 + x*a2^3 + a2^3

By the way, note that the field GF(2^3) is well defined in Sage:

sage: F.<x> = GF(2^3)
sage: F
Finite Field in x of size 2^3
sage: x.minpoly()
x^3 + x + 1
sage: R.<a0,a1,a2> = PolynomialRing(F)
sage: f(a0*+a1*x+a2*x)
(x + 1)*a0^3*a1^3 + (x + 1)*a0^2*a1^2*a2 + (x + 1)*a0*a1*a2^2 + (x + 1)*a2^3

EDIT

Note that since you work on a field of characteristic 2, you necessarily have ai + ai = 0:

sage: a0+a0
0

If you want your variables to also satisfy ai^2 = ai, you can just add this condition when you define the quotient ring:

sage: sage: GF23.<x,a0,a1,a2> = P_GF2.quotient_ring([X^3+X+1, A0^2+A0, A1^2+A1, A2^2+A2])
sage: GF23
Quotient of Multivariate Polynomial Ring in X, A0, A1, A2 over Finite Field of size 2 by the ideal (X^3 + X + 1, A0^2 + A0, A1^2 + A1, A2^2 + A2)
sage: a0^2
a0
sage: a0^3+a0
0
sage: f(a0*+a1*x+a2*x)
x*a0*a1 + a0*a1 + x*a2 + a2
more

This is most helpful, but there is a detail still missing: what I wanted is a way for a0, a1 and a2 to be treated as generic elements of GF(2). Meaning for example, that $a_i^n=a_i$ and $a_i+a_i = 0$. Without this, the resulting expression is needlessly complicated. Can it be achieved?

( 2016-08-06 05:39:12 -0600 )edit

( 2016-08-06 14:46:55 -0600 )edit

I accepted this answer because, well, it fully answers my question. But now I must ask for what would truly be the cherry on top of the cake: is there any way to group the result by 'x'? I.e. to make the result of your example look like x*(a0*a1+a2) + a0*a1 + a2? I tried these methods, but they don't work. The closest I can get is sorted(r.monomials()), where r is the produced result. Again, thank you in advance.

( 2016-08-07 05:41:55 -0600 )edit

Should I have asked another question for this?

( 2016-08-10 02:09:36 -0600 )edit

@mksanders, sure, why don't you ask a follow-up question. For reference, you can state in the new question that it is a follow-up to http://ask.sagemath.org/question/3433... .

( 2016-08-23 03:04:40 -0600 )edit