ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 23 Aug 2016 10:04:40 +0200Symbolic calculations in finite field extensionhttps://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/ Hello,
Please consider the following code snippet:
<pre><code>
P_GF2.<X> = PolynomialRing(GF(2))
GF23.<x> = P_GF2.quotient_ring(X^3+X+1)
def f(val):
return val**3
</code></pre>
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.Thu, 04 Aug 2016 17:07:17 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/Answer by tmonteil for <p>Hello,</p>
<p>Please consider the following code snippet:</p>
<pre><code>
P_GF2.<X> = PolynomialRing(GF(2))
GF23.<x> = P_GF2.quotient_ring(X^3+X+1)
def f(val):
return val**3
</code></pre>
<p>This works as expected, when <code>val</code> is something like $1+x+x^2$. What I wanted to do is to calculate the value of $f$, but using a <em>generic</em> 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?</p>
<p>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.</p>
<p>Thank you very much in advance.</p>
https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?answer=34333#post-id-34333Instead 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
Fri, 05 Aug 2016 05:21:49 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?answer=34333#post-id-34333Comment by mksanders for <p>Instead of symbolic variables, you can define the <code>ai</code> as polynomial indeterminates, as follows:</p>
<pre><code>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
</code></pre>
<p>By the way, note that the field <code>GF(2^3)</code> is well defined in Sage:</p>
<pre><code>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
</code></pre>
<p><strong>EDIT</strong></p>
<p>Note that since you work on a field of characteristic 2, you necessarily have <code>ai + ai = 0</code>:</p>
<pre><code>sage: a0+a0
0
</code></pre>
<p>If you want your variables to also satisfy <code>ai^2 = ai</code>, you can just add this condition when you define the quotient ring:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34352#post-id-34352This 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?Sat, 06 Aug 2016 12:39:12 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34352#post-id-34352Comment by tmonteil for <p>Instead of symbolic variables, you can define the <code>ai</code> as polynomial indeterminates, as follows:</p>
<pre><code>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
</code></pre>
<p>By the way, note that the field <code>GF(2^3)</code> is well defined in Sage:</p>
<pre><code>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
</code></pre>
<p><strong>EDIT</strong></p>
<p>Note that since you work on a field of characteristic 2, you necessarily have <code>ai + ai = 0</code>:</p>
<pre><code>sage: a0+a0
0
</code></pre>
<p>If you want your variables to also satisfy <code>ai^2 = ai</code>, you can just add this condition when you define the quotient ring:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34358#post-id-34358I updated my answer.Sat, 06 Aug 2016 21:46:55 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34358#post-id-34358Comment by mksanders for <p>Instead of symbolic variables, you can define the <code>ai</code> as polynomial indeterminates, as follows:</p>
<pre><code>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
</code></pre>
<p>By the way, note that the field <code>GF(2^3)</code> is well defined in Sage:</p>
<pre><code>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
</code></pre>
<p><strong>EDIT</strong></p>
<p>Note that since you work on a field of characteristic 2, you necessarily have <code>ai + ai = 0</code>:</p>
<pre><code>sage: a0+a0
0
</code></pre>
<p>If you want your variables to also satisfy <code>ai^2 = ai</code>, you can just add this condition when you define the quotient ring:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34363#post-id-34363I 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](http://ask.sagemath.org/question/9116/polynomial-distribute-to-greatest-common-factor/) 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.Sun, 07 Aug 2016 12:41:55 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34363#post-id-34363Comment by mksanders for <p>Instead of symbolic variables, you can define the <code>ai</code> as polynomial indeterminates, as follows:</p>
<pre><code>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
</code></pre>
<p>By the way, note that the field <code>GF(2^3)</code> is well defined in Sage:</p>
<pre><code>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
</code></pre>
<p><strong>EDIT</strong></p>
<p>Note that since you work on a field of characteristic 2, you necessarily have <code>ai + ai = 0</code>:</p>
<pre><code>sage: a0+a0
0
</code></pre>
<p>If you want your variables to also satisfy <code>ai^2 = ai</code>, you can just add this condition when you define the quotient ring:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34398#post-id-34398Should I have asked another question for this?Wed, 10 Aug 2016 09:09:36 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34398#post-id-34398Comment by slelievre for <p>Instead of symbolic variables, you can define the <code>ai</code> as polynomial indeterminates, as follows:</p>
<pre><code>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
</code></pre>
<p>By the way, note that the field <code>GF(2^3)</code> is well defined in Sage:</p>
<pre><code>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
</code></pre>
<p><strong>EDIT</strong></p>
<p>Note that since you work on a field of characteristic 2, you necessarily have <code>ai + ai = 0</code>:</p>
<pre><code>sage: a0+a0
0
</code></pre>
<p>If you want your variables to also satisfy <code>ai^2 = ai</code>, you can just add this condition when you define the quotient ring:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34566#post-id-34566@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/34330/symbolic-calculations-in-finite-field-extension/ .Tue, 23 Aug 2016 10:04:40 +0200https://ask.sagemath.org/question/34330/symbolic-calculations-in-finite-field-extension/?comment=34566#post-id-34566