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.Sat, 06 Nov 2021 22:37:18 +0100Creating a multivariate polynomial with idealhttps://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/ Hello,
new user of sage here. I have a computation not too difficult too make, but I am a bit lost since it is above my math level and before the vastness of sage documentation.
I have to create and do a multiplication with a "multivariate polynomial which is an element of a polynomial quotient ring defined by the polynomial
ring over GF(2)[x, y, z] modulo the ideal generated by ⟨ $1+x^5$, $1+y^5$, $1+z^{64}$⟩".
I already wrote this:
Ring = PolynomialRing(GF(Integer(2)), ['x', 'y', 'z'])
P = Ring; (x, y, z,) = P._first_ngens(3)
I = P.ideal([Integer(1)+x**Integer(5), Integer(1)+y**Integer(5), Integer(1)+z**Integer(64)])
but don't know how to continue or if it is correct.
How should I proceed ? Thank you.
Thu, 04 Nov 2021 22:37:30 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/Comment by Max Alekseyev for <p>Hello,
new user of sage here. I have a computation not too difficult too make, but I am a bit lost since it is above my math level and before the vastness of sage documentation.</p>
<p>I have to create and do a multiplication with a "multivariate polynomial which is an element of a polynomial quotient ring defined by the polynomial
ring over GF(2)[x, y, z] modulo the ideal generated by ⟨ $1+x^5$, $1+y^5$, $1+z^{64}$⟩".</p>
<p>I already wrote this:</p>
<pre><code>Ring = PolynomialRing(GF(Integer(2)), ['x', 'y', 'z'])
P = Ring; (x, y, z,) = P._first_ngens(3)
I = P.ideal([Integer(1)+x**Integer(5), Integer(1)+y**Integer(5), Integer(1)+z**Integer(64)])
</code></pre>
<p>but don't know how to continue or if it is correct. </p>
<p>How should I proceed ? Thank you.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59599#post-id-59599`Integer()` can be omitted everrywhere.Fri, 05 Nov 2021 15:24:12 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59599#post-id-59599Answer by Max Alekseyev for <p>Hello,
new user of sage here. I have a computation not too difficult too make, but I am a bit lost since it is above my math level and before the vastness of sage documentation.</p>
<p>I have to create and do a multiplication with a "multivariate polynomial which is an element of a polynomial quotient ring defined by the polynomial
ring over GF(2)[x, y, z] modulo the ideal generated by ⟨ $1+x^5$, $1+y^5$, $1+z^{64}$⟩".</p>
<p>I already wrote this:</p>
<pre><code>Ring = PolynomialRing(GF(Integer(2)), ['x', 'y', 'z'])
P = Ring; (x, y, z,) = P._first_ngens(3)
I = P.ideal([Integer(1)+x**Integer(5), Integer(1)+y**Integer(5), Integer(1)+z**Integer(64)])
</code></pre>
<p>but don't know how to continue or if it is correct. </p>
<p>How should I proceed ? Thank you.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?answer=59609#post-id-59609Inverting a polynomial modulo an ideal can be done by using `.inverse_mod()` method - like in the example below:
R.<x,y,z> = PolynomialRing(GF(2))
I = R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
(1+x+y).inverse_mod(I)
which gives inversion of `1+x+y` modulo `I` as `x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1`.Sat, 06 Nov 2021 14:47:22 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?answer=59609#post-id-59609Comment by Max Alekseyev for <p>Inverting a polynomial modulo an ideal can be done by using <code>.inverse_mod()</code> method - like in the example below:</p>
<pre><code>R.<x,y,z> = PolynomialRing(GF(2))
I = R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
(1+x+y).inverse_mod(I)
</code></pre>
<p>which gives inversion of <code>1+x+y</code> modulo <code>I</code> as <code>x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59618#post-id-59618In fact, this functionality is already implemented in Sage - I've updated my answer.Sat, 06 Nov 2021 22:37:18 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59618#post-id-59618Comment by Katoptriss for <p>Inverting a polynomial modulo an ideal can be done by using <code>.inverse_mod()</code> method - like in the example below:</p>
<pre><code>R.<x,y,z> = PolynomialRing(GF(2))
I = R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
(1+x+y).inverse_mod(I)
</code></pre>
<p>which gives inversion of <code>1+x+y</code> modulo <code>I</code> as <code>x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59617#post-id-59617Perfect, thank you very much for all your help!Sat, 06 Nov 2021 22:31:11 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59617#post-id-59617Answer by tmonteil for <p>Hello,
new user of sage here. I have a computation not too difficult too make, but I am a bit lost since it is above my math level and before the vastness of sage documentation.</p>
<p>I have to create and do a multiplication with a "multivariate polynomial which is an element of a polynomial quotient ring defined by the polynomial
ring over GF(2)[x, y, z] modulo the ideal generated by ⟨ $1+x^5$, $1+y^5$, $1+z^{64}$⟩".</p>
<p>I already wrote this:</p>
<pre><code>Ring = PolynomialRing(GF(Integer(2)), ['x', 'y', 'z'])
P = Ring; (x, y, z,) = P._first_ngens(3)
I = P.ideal([Integer(1)+x**Integer(5), Integer(1)+y**Integer(5), Integer(1)+z**Integer(64)])
</code></pre>
<p>but don't know how to continue or if it is correct. </p>
<p>How should I proceed ? Thank you.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?answer=59597#post-id-59597You can then create the quotient of P by I as follows:
sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
You can then work in the quotient as follows:
sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
As you can see, `xbar^6` was replaced by `xbar`.
Fri, 05 Nov 2021 13:45:00 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?answer=59597#post-id-59597Comment by Max Alekseyev for <p>You can then create the quotient of P by I as follows:</p>
<pre><code>sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
</code></pre>
<p>You can then work in the quotient as follows:</p>
<pre><code>sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
</code></pre>
<p>As you can see, <code>xbar^6</code> was replaced by <code>xbar</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59610#post-id-59610I've explained how to invert polynomials modulo $I$ in the answer below.Sat, 06 Nov 2021 14:49:15 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59610#post-id-59610Comment by Max Alekseyev for <p>You can then create the quotient of P by I as follows:</p>
<pre><code>sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
</code></pre>
<p>You can then work in the quotient as follows:</p>
<pre><code>sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
</code></pre>
<p>As you can see, <code>xbar^6</code> was replaced by <code>xbar</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59604#post-id-59604Well, perhaps some clarification is needed for what you want to achieve. Is the polynomial you are inverting actually invertible in `Q`, or you want to to get result as a fraction? Can you give an example?Fri, 05 Nov 2021 23:13:18 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59604#post-id-59604Comment by Katoptriss for <p>You can then create the quotient of P by I as follows:</p>
<pre><code>sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
</code></pre>
<p>You can then work in the quotient as follows:</p>
<pre><code>sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
</code></pre>
<p>As you can see, <code>xbar^6</code> was replaced by <code>xbar</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59605#post-id-59605I guess it is invertible, yes. It is the Q one at the very end of the page 18 here : https://keccak.team/files/Keccak-reference-3.0.pdf. The context is that there is a function named theta whose operation can be viewed as a multiplication by a polynomial (2.1, just above). With the help of this thread, I managed to succeed at doing this. But I'm interested in doing the reverse operation, so I need this polynomial Q that I have trouble defining using sage. My aim is only to define it and multiply it with another polynomial that I already have.Fri, 05 Nov 2021 23:26:03 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59605#post-id-59605Comment by Katoptriss for <p>You can then create the quotient of P by I as follows:</p>
<pre><code>sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
</code></pre>
<p>You can then work in the quotient as follows:</p>
<pre><code>sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
</code></pre>
<p>As you can see, <code>xbar^6</code> was replaced by <code>xbar</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59603#post-id-59603It gives me a TypeError : self must be an integral domain. Update : I also tried the inverse_of_unit() builtin of a polynomial of Q, but it doesn't seem to give the correct answer, as $P^{-1} * P$ != 1.Fri, 05 Nov 2021 21:52:42 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59603#post-id-59603Comment by Max Alekseyev for <p>You can then create the quotient of P by I as follows:</p>
<pre><code>sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
</code></pre>
<p>You can then work in the quotient as follows:</p>
<pre><code>sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
</code></pre>
<p>As you can see, <code>xbar^6</code> was replaced by <code>xbar</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59602#post-id-59602Define `R = Q.fraction_field()` and then you can compute `R(f)^(-1)` for any `f` in `Q`.Fri, 05 Nov 2021 21:38:57 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59602#post-id-59602Comment by Katoptriss for <p>You can then create the quotient of P by I as follows:</p>
<pre><code>sage: Q = P.quotient(I)
sage: Q
Quotient of Multivariate Polynomial Ring in x, y, z over Finite Field of size 2 by the ideal (x^5 + 1, y^5 + 1, z^64 + 1)
</code></pre>
<p>You can then work in the quotient as follows:</p>
<pre><code>sage: A = Q(x^4+x*y^2)
sage: A
xbar^4 + xbar*ybar^2
sage: B = Q(x^2)
sage: B
xbar^2
sage: A * B
xbar^3*ybar^2 + xbar
</code></pre>
<p>As you can see, <code>xbar^6</code> was replaced by <code>xbar</code>.</p>
https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59600#post-id-59600Thank you, it worked fine. Another question: how could I create a polynomial of the same nature, power -1 ? It tells me "fraction must have unit denominator". A quick search tells me to look at sage's xgcd, but it is not an attribute of the class used here. EDIT : I tried to add `P = R.fraction_field()`, but now every polynomial I define is equal to 0.Fri, 05 Nov 2021 16:11:11 +0100https://ask.sagemath.org/question/59594/creating-a-multivariate-polynomial-with-ideal/?comment=59600#post-id-59600