Ask Your Question
1

Symbolic arithmetic in finite fields

asked 2019-12-30 21:41:09 -0600

Virendra gravatar image

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 flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
0

answered 2019-12-31 03:55:05 -0600

tmonteil gravatar image

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 ?

edit flag offensive delete link more

Comments

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.

Virendra gravatar imageVirendra ( 2019-12-31 06:20:15 -0600 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2019-12-30 21:41:09 -0600

Seen: 102 times

Last updated: Dec 31 '19