# Symbolic arithmetic in finite fields

I want to know whether and how we can perform symbolic arithmetic for finite fields in SAGEmath. Let me explain the problem. Let GF(2^n) be a finite field extension of GF(2) with a polynomial basis with respect to a root 'a' of an irreducible polynomial. My questions are:

1. How to declare an indeterminate element x in this field with symbolic co-ordinates xi, i=1..n in GF(2).
2. If x,y are indeterminates how to compute x^2, xy, xy^2 etc as functions symbolically. In other words, how to extract symbolic co-ordinates of these functions.
edit retag close merge delete

Sort by » oldest newest most voted

Regarding 1:

You can define the field, and simultaneously associate a python name to its generator with:

sage: K.<a> = GF(2^5)
sage: a^31
1
sage: a.parent()
Finite Field in a of size 2^5
sage: a.minpoly()
x^5 + x^2 + 1


So, you can construct any element as the sum of powers of a:

sage: x
a^4 + a^3 + 1
sage: x.parent()
Finite Field in a of size 2^5


Conversely, given an element x in K, you can turn it into a polynomial in a and then extract its coefficients:

sage: x = K.random_element() ; x
a^3 + a^2 + 1
sage: x.parent()
Finite Field in a of size 2^5
sage: x.polynomial()
a^3 + a^2 + 1
sage: x.polynomial().parent()
Univariate Polynomial Ring in a over Finite Field of size 2 (using GF2X)
sage: D = x.polynomial().dict() ; D
{0: 1, 2: 1, 3: 1}


And get back x from it:

sage: [D[d]*a^d for d in D]
[1, a^2, a^3]
sage: sum(D[d]*a^d for d in D)
a^3 + a^2 + 1
sage: sum(D[d]*a^d for d in D) == x
True


Regarding 2: i am not sure to understand you query, the function is not linear, so i do not see how do you want to represent it, could you please provide an example of what do you expect ?

more

Thanks for the answer. But what you have shown is arithmetic operations and extraction of co-ordinates of given elements of the field. What I am asking is if an indeterminate x belongs to the field of size 2^5 and is represented in a chosen basis then x has indeterminate co-ordinates xi in GF(2) wrt that basis. What I want is to compute symbolic co-ordinates of x^2, x^3, xy etc. in the same basis. These co-ordinates will be polynomial functions of co-ordinates of x,y.

( 2019-12-31 13:20:15 +0200 )edit