Creating a multivariate polynomial with ideal

Katoptriss
13 ●2 ●6

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.

Comments

Integer() can be omitted everrywhere.

Max Alekseyev ( 3 years ago )

add a comment

2 Answers

Sort by » oldest newest most voted

answered 3 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

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.

link

Comments

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.

Katoptriss ( 3 years ago )

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

Max Alekseyev ( 3 years ago )

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.

Katoptriss ( 3 years ago )

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?

Max Alekseyev ( 3 years ago )

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.

Katoptriss ( 3 years ago )

see more comments

answered 3 years ago

Max Alekseyev

6932 ●9 ●52 ●162

updated 3 years ago

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.

link

Comments

Perfect, thank you very much for all your help!

Katoptriss ( 3 years ago )

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

Max Alekseyev ( 3 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Creating a multivariate polynomial with ideal

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Creating a multivariate polynomial with ideal savecancel

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Creating a multivariate polynomial with ideal