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}$⟩".

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.

edit retag close merge delete

Integer() can be omitted everrywhere.

( 2021-11-05 15:24:12 +0200 )edit

Sort by » oldest newest most voted

Inverting 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.

more

Perfect, thank you very much for all your help!

( 2021-11-06 22:31:11 +0200 )edit

In fact, this functionality is already implemented in Sage - I've updated my answer.

( 2021-11-06 22:37:18 +0200 )edit

You 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.

more

Thank 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.

( 2021-11-05 16:11:11 +0200 )edit

Define R = Q.fraction_field() and then you can compute R(f)^(-1) for any f in Q.

( 2021-11-05 21:38:57 +0200 )edit

It 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.

( 2021-11-05 21:52:42 +0200 )edit

Well, 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?

( 2021-11-05 23:13:18 +0200 )edit

I guess it is invertible, yes. It is the Q one at the very end of the page 18 here : https://keccak.team/files/Keccak-refe.... 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.

( 2021-11-05 23:26:03 +0200 )edit