Ask Your Question

Symbolic computions in a finite field

asked 2013-07-21 22:49:28 -0500

Johan gravatar image

updated 2013-07-24 01:46:35 -0500


I am interested in symbolic computations in a file field. Working in the field $GF(2^8)$ with $x$ as a generator and a variable $y$, also there is a function $f:GF(2^8)\rightarrow GF(2^8)$ of which the exact definition is not given. Can sage do the following:

$(x + y) ^ {2^8} \mapsto x + y$

$(x + y) ^ {2^6} \mapsto x ^ {2^6} + y ^ {2^6}$

$f(y) + f(y) \mapsto 0\cdot x$

If sage cannot do it does there exist another program which can?

Below is my question updated:

For the function I have a partial solution but I cannot mix it with an element of an finite field

import sympy
f = sympy.Function('f')
y = var('y')
sympy.expand((f(y)+f(y)), modulus=2)

When I want to add an element of a finite field

import sympy
f = sympy.Function('f')
x = GF(2^8,'x').gen()
f(x) + x

the statement $f(x) +x$ give me an error that makes sense ... TypeError: unsupported operand parent(s) for '+': 'f' and 'Finite Field in g of size 2^8'

To create a variable in a finite field I decided to use a Polynomial ring

import sympy
f = sympy.Function('f')
R.< x > = PolynomialRing(GF(2))
f(x) + x

both $f(x)$ and $f(x) + x$ fails with a very long Trace message.


edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2013-07-23 23:54:37 -0500

updated 2013-07-24 04:30:39 -0500

I'll call K the field GF(2^8), a its generator, and x a generic element of K.

sage: K.<a> = GF(2^8,'a')

Isn't there a problem with your first equation?

(1)    f((a+x)^(2^8-1)) = a + x

This is saying (changing x to x + a) that for every x in K, f(x^(2^8-1)) equals x.

Since for any nonzero x in K, x^(2^8-1) equals 1,

sage: all((x == 0 or x^(2^8-1) == 1) for x in K)

this is saying that f(0) equals 0 and that for every nonzero x in K, f(1) equals x.

No well-defined function from K to K can satisfy that!


The new form of your first equation (with exponent (2^8) instead of (2^8-1)):

(1)    f((a+x)^(2^8)) = a + x

is saying that for every x in K, you have f(x) = x. Indeed,

sage: all(x^(2^8) == x for x in K)

Equation (3) is void, since, given that f(x) is in K, of characteristic 2, obviously f(x) + f(x) equals 0 for any x in K.

Equation (2) is saying that for any x in K, f(x^(2^6)) equals (x+a)^(2^6) + a^(2^6). This is saying that f is the identity when restricted to (2^6)-th powers:

sage: all(x^(2^6) == (x+a)^(2^6) + a^(2^6) for x in K)

so it is a priori weaker than equation (1), except that the map sending x to x^(2^6) is in fact a bijection from K to K:

sage: len(set(x^(2^6) for x in K)) == len(K)

so equation (2) is also saying that f is the identity map on K.

In the end, for the purpose of your exercise, using Sage for small computations in K was enough, and manipulating an undefined function from K to K was not needed.

edit flag offensive delete link more


@slelievre Thanx it was suppose to be x^(2^8), I have updated the question

Johan gravatar imageJohan ( 2013-07-24 01:45:51 -0500 )edit

I updated the answer.

slelievre gravatar imageslelievre ( 2013-07-24 06:22:05 -0500 )edit

My requirement is to be able to use unknowns and function (not fully defined) in equations over a specific finite field. The only knowledge about the unknowns is that the unknown is in the field. Also the range and domain of the function f is the field. In the end I want to use sage as a calculator to perform arithmetic in a finite field to simplify a set of equations. These equation is not linear and that where the function f comes in, it will be used to represent a non-linear function.

Johan gravatar imageJohan ( 2013-07-24 11:29:57 -0500 )edit

answered 2013-07-23 09:39:23 -0500

One way to obtain x + f(x) is as follows:

sage: import sympy
sage: f = sympy.Function('f')
sage: g(x) = x
sage: f(x) + g(x)
x + f(x)

I'm not sure how to mix this with your finite field problem.

edit flag offensive delete link more


What type of code do I need to write to be able to write something like f = sympy.Function('f') y + f(y^6) + f(x^2) + x where y is an element in a finite field and x is a variable/Symbol. If I was working in c++ I would at least to overload the + operator between the FiniteField sympy.Function can sympy.Symbol types.

Johan gravatar imageJohan ( 2013-07-29 02:14:15 -0500 )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

1 follower


Asked: 2013-07-21 22:49:28 -0500

Seen: 670 times

Last updated: Jul 24 '13