Creating a multivariate polynomial with ideal

asked 2021-11-04 22:37:30 +0100

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.

edit retag flag offensive close merge delete

Comments

Integer() can be omitted everrywhere.

Max Alekseyev ( 2021-11-05 15:24:12 +0100 )edit

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2021-11-05 13:45:00 +0100

tmonteil
27423 ●31 ●204 ●517 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.

edit flag offensive delete 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 ( 2021-11-05 16:11:11 +0100 )edit

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

Max Alekseyev ( 2021-11-05 21:38:57 +0100 )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.

Katoptriss ( 2021-11-05 21:52:42 +0100 )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?

Max Alekseyev ( 2021-11-05 23:13:18 +0100 )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.

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

see more comments

answered 2021-11-06 14:47:22 +0100

Max Alekseyev

6560 ●9 ●47 ●155

updated 2021-11-06 22:37:54 +0100

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.

edit flag offensive delete link

Comments

Perfect, thank you very much for all your help!

Katoptriss ( 2021-11-06 22:31:11 +0100 )edit

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

Max Alekseyev ( 2021-11-06 22:37:18 +0100 )edit

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 edit

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Creating a multivariate polynomial with ideal