ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 29 Jul 2013 02:14:15 -0500Symbolic computations in a finite fieldhttp://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/Hallo
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
<pre>
<code>
import sympy
f = sympy.Function('f')
y = var('y')
sympy.expand((f(y)+f(y)), modulus=2)
</code>
</pre>
When I want to add an element of a finite field
<pre>
<code>
import sympy
f = sympy.Function('f')
x = GF(2^8,'x').gen()
f(x)
f(x) + x
</code>
</pre>
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
<pre>
<code>
import sympy
f = sympy.Function('f')
R.< x > = PolynomialRing(GF(2))
f(x)
f(x) + x
</code>
</pre>
both $f(x)$ and $f(x) + x$ fails with a very long Trace message.
RegardsSun, 21 Jul 2013 22:49:28 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/Answer by slelievre for <p>Hallo</p>
<p>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:</p>
<p>$(x + y) ^ {2^8} \mapsto x + y$</p>
<p>$(x + y) ^ {2^6} \mapsto x ^ {2^6} + y ^ {2^6}$</p>
<p>$f(y) + f(y) \mapsto 0\cdot x$</p>
<p>If sage cannot do it does there exist another program which can?</p>
<hr>
<p>Below is my question updated:</p>
<p>For the function I have a partial solution but I cannot mix it with an element of an finite field</p>
<pre><code>
import sympy
f = sympy.Function('f')
y = var('y')
sympy.expand((f(y)+f(y)), modulus=2)
</code>
</pre>
<p>When I want to add an element of a finite field</p>
<pre><code>
import sympy
f = sympy.Function('f')
x = GF(2^8,'x').gen()
f(x)
f(x) + x
</code>
</pre>
<p>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'</p>
<p>To create a variable in a finite field I decided to use a Polynomial ring</p>
<pre><code>
import sympy
f = sympy.Function('f')
R.< x > = PolynomialRing(GF(2))
f(x)
f(x) + x
</code>
</pre>
<p>both $f(x)$ and $f(x) + x$ fails with a very long Trace message.</p>
<p>Regards</p>
http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?answer=15271#post-id-15271One 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.Tue, 23 Jul 2013 09:39:23 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?answer=15271#post-id-15271Comment by Johan for <p>One way to obtain <code>x + f(x)</code> is as follows:</p>
<pre><code>sage: import sympy
sage: f = sympy.Function('f')
sage: g(x) = x
sage: f(x) + g(x)
x + f(x)
</code></pre>
<p>I'm not sure how to mix this with your finite field problem.</p>
http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17221#post-id-17221What 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.Mon, 29 Jul 2013 02:14:15 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17221#post-id-17221Answer by slelievre for <p>Hallo</p>
<p>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:</p>
<p>$(x + y) ^ {2^8} \mapsto x + y$</p>
<p>$(x + y) ^ {2^6} \mapsto x ^ {2^6} + y ^ {2^6}$</p>
<p>$f(y) + f(y) \mapsto 0\cdot x$</p>
<p>If sage cannot do it does there exist another program which can?</p>
<hr>
<p>Below is my question updated:</p>
<p>For the function I have a partial solution but I cannot mix it with an element of an finite field</p>
<pre><code>
import sympy
f = sympy.Function('f')
y = var('y')
sympy.expand((f(y)+f(y)), modulus=2)
</code>
</pre>
<p>When I want to add an element of a finite field</p>
<pre><code>
import sympy
f = sympy.Function('f')
x = GF(2^8,'x').gen()
f(x)
f(x) + x
</code>
</pre>
<p>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'</p>
<p>To create a variable in a finite field I decided to use a Polynomial ring</p>
<pre><code>
import sympy
f = sympy.Function('f')
R.< x > = PolynomialRing(GF(2))
f(x)
f(x) + x
</code>
</pre>
<p>both $f(x)$ and $f(x) + x$ fails with a very long Trace message.</p>
<p>Regards</p>
http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?answer=15273#post-id-15273I'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)
True
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!
EDIT:
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)
True
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)
True
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)
True
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.Tue, 23 Jul 2013 23:54:37 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?answer=15273#post-id-15273Comment by Johan for <p>I'll call <code>K</code> the field <code>GF(2^8)</code>, <code>a</code> its generator, and <code>x</code> a generic element of <code>K</code>.</p>
<pre><code>sage: K.<a> = GF(2^8,'a')
</code></pre>
<p>Isn't there a problem with your first equation?</p>
<pre><code>(1) f((a+x)^(2^8-1)) = a + x
</code></pre>
<p>This is saying (changing x to x + a) that
for every <code>x</code> in <code>K</code>, <code>f(x^(2^8-1))</code> equals <code>x</code>.</p>
<p>Since for any nonzero <code>x</code> in <code>K</code>, <code>x^(2^8-1)</code> equals <code>1</code>,</p>
<pre><code>sage: all((x == 0 or x^(2^8-1) == 1) for x in K)
True
</code></pre>
<p>this is saying that <code>f(0)</code> equals <code>0</code> and that
for every nonzero <code>x</code> in <code>K</code>, <code>f(1)</code> equals <code>x</code>.</p>
<p>No well-defined function from <code>K</code> to <code>K</code> can satisfy that!</p>
<p>EDIT:</p>
<p>The new form of your first equation (with exponent <code>(2^8)</code> instead of <code>(2^8-1)</code>):</p>
<pre><code>(1) f((a+x)^(2^8)) = a + x
</code></pre>
<p>is saying that for every <code>x</code> in <code>K</code>, you have <code>f(x) = x</code>. Indeed,</p>
<pre><code>sage: all(x^(2^8) == x for x in K)
True
</code></pre>
<p>Equation (3) is void, since, given that <code>f(x)</code> is in <code>K</code>, of characteristic <code>2</code>, obviously <code>f(x) + f(x)</code> equals <code>0</code> for any <code>x</code> in <code>K</code>.</p>
<p>Equation (2) is saying that for any <code>x</code> in <code>K</code>, <code>f(x^(2^6))</code> equals <code>(x+a)^(2^6) + a^(2^6)</code>. This is saying that <code>f</code> is the identity when restricted to <code>(2^6)</code>-th powers:</p>
<pre><code>sage: all(x^(2^6) == (x+a)^(2^6) + a^(2^6) for x in K)
True
</code></pre>
<p>so it is a priori weaker than equation (1), except that the map sending <code>x</code> to <code>x^(2^6)</code> is in fact a bijection from <code>K</code> to <code>K</code>:</p>
<pre><code>sage: len(set(x^(2^6) for x in K)) == len(K)
True
</code></pre>
<p>so equation (2) is also saying that <code>f</code> is the identity map on <code>K</code>.</p>
<p>In the end, for the purpose of your exercise, using Sage for small computations in <code>K</code> was enough, and manipulating an undefined function from <code>K</code> to <code>K</code> was not needed.</p>
http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17242#post-id-17242My 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.Wed, 24 Jul 2013 11:29:57 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17242#post-id-17242Comment by Johan for <p>I'll call <code>K</code> the field <code>GF(2^8)</code>, <code>a</code> its generator, and <code>x</code> a generic element of <code>K</code>.</p>
<pre><code>sage: K.<a> = GF(2^8,'a')
</code></pre>
<p>Isn't there a problem with your first equation?</p>
<pre><code>(1) f((a+x)^(2^8-1)) = a + x
</code></pre>
<p>This is saying (changing x to x + a) that
for every <code>x</code> in <code>K</code>, <code>f(x^(2^8-1))</code> equals <code>x</code>.</p>
<p>Since for any nonzero <code>x</code> in <code>K</code>, <code>x^(2^8-1)</code> equals <code>1</code>,</p>
<pre><code>sage: all((x == 0 or x^(2^8-1) == 1) for x in K)
True
</code></pre>
<p>this is saying that <code>f(0)</code> equals <code>0</code> and that
for every nonzero <code>x</code> in <code>K</code>, <code>f(1)</code> equals <code>x</code>.</p>
<p>No well-defined function from <code>K</code> to <code>K</code> can satisfy that!</p>
<p>EDIT:</p>
<p>The new form of your first equation (with exponent <code>(2^8)</code> instead of <code>(2^8-1)</code>):</p>
<pre><code>(1) f((a+x)^(2^8)) = a + x
</code></pre>
<p>is saying that for every <code>x</code> in <code>K</code>, you have <code>f(x) = x</code>. Indeed,</p>
<pre><code>sage: all(x^(2^8) == x for x in K)
True
</code></pre>
<p>Equation (3) is void, since, given that <code>f(x)</code> is in <code>K</code>, of characteristic <code>2</code>, obviously <code>f(x) + f(x)</code> equals <code>0</code> for any <code>x</code> in <code>K</code>.</p>
<p>Equation (2) is saying that for any <code>x</code> in <code>K</code>, <code>f(x^(2^6))</code> equals <code>(x+a)^(2^6) + a^(2^6)</code>. This is saying that <code>f</code> is the identity when restricted to <code>(2^6)</code>-th powers:</p>
<pre><code>sage: all(x^(2^6) == (x+a)^(2^6) + a^(2^6) for x in K)
True
</code></pre>
<p>so it is a priori weaker than equation (1), except that the map sending <code>x</code> to <code>x^(2^6)</code> is in fact a bijection from <code>K</code> to <code>K</code>:</p>
<pre><code>sage: len(set(x^(2^6) for x in K)) == len(K)
True
</code></pre>
<p>so equation (2) is also saying that <code>f</code> is the identity map on <code>K</code>.</p>
<p>In the end, for the purpose of your exercise, using Sage for small computations in <code>K</code> was enough, and manipulating an undefined function from <code>K</code> to <code>K</code> was not needed.</p>
http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17248#post-id-17248@slelievre Thanx
it was suppose to be x^(2^8), I have updated the questionWed, 24 Jul 2013 01:45:51 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17248#post-id-17248Comment by slelievre for <p>I'll call <code>K</code> the field <code>GF(2^8)</code>, <code>a</code> its generator, and <code>x</code> a generic element of <code>K</code>.</p>
<pre><code>sage: K.<a> = GF(2^8,'a')
</code></pre>
<p>Isn't there a problem with your first equation?</p>
<pre><code>(1) f((a+x)^(2^8-1)) = a + x
</code></pre>
<p>This is saying (changing x to x + a) that
for every <code>x</code> in <code>K</code>, <code>f(x^(2^8-1))</code> equals <code>x</code>.</p>
<p>Since for any nonzero <code>x</code> in <code>K</code>, <code>x^(2^8-1)</code> equals <code>1</code>,</p>
<pre><code>sage: all((x == 0 or x^(2^8-1) == 1) for x in K)
True
</code></pre>
<p>this is saying that <code>f(0)</code> equals <code>0</code> and that
for every nonzero <code>x</code> in <code>K</code>, <code>f(1)</code> equals <code>x</code>.</p>
<p>No well-defined function from <code>K</code> to <code>K</code> can satisfy that!</p>
<p>EDIT:</p>
<p>The new form of your first equation (with exponent <code>(2^8)</code> instead of <code>(2^8-1)</code>):</p>
<pre><code>(1) f((a+x)^(2^8)) = a + x
</code></pre>
<p>is saying that for every <code>x</code> in <code>K</code>, you have <code>f(x) = x</code>. Indeed,</p>
<pre><code>sage: all(x^(2^8) == x for x in K)
True
</code></pre>
<p>Equation (3) is void, since, given that <code>f(x)</code> is in <code>K</code>, of characteristic <code>2</code>, obviously <code>f(x) + f(x)</code> equals <code>0</code> for any <code>x</code> in <code>K</code>.</p>
<p>Equation (2) is saying that for any <code>x</code> in <code>K</code>, <code>f(x^(2^6))</code> equals <code>(x+a)^(2^6) + a^(2^6)</code>. This is saying that <code>f</code> is the identity when restricted to <code>(2^6)</code>-th powers:</p>
<pre><code>sage: all(x^(2^6) == (x+a)^(2^6) + a^(2^6) for x in K)
True
</code></pre>
<p>so it is a priori weaker than equation (1), except that the map sending <code>x</code> to <code>x^(2^6)</code> is in fact a bijection from <code>K</code> to <code>K</code>:</p>
<pre><code>sage: len(set(x^(2^6) for x in K)) == len(K)
True
</code></pre>
<p>so equation (2) is also saying that <code>f</code> is the identity map on <code>K</code>.</p>
<p>In the end, for the purpose of your exercise, using Sage for small computations in <code>K</code> was enough, and manipulating an undefined function from <code>K</code> to <code>K</code> was not needed.</p>
http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17245#post-id-17245I updated the answer.Wed, 24 Jul 2013 06:22:05 -0500http://ask.sagemath.org/question/10371/symbolic-computations-in-a-finite-field/?comment=17245#post-id-17245