Ask Your Question
1

Creating a multivariate polynomial with ideal

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

Katoptriss gravatar image

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 gravatar imageMax Alekseyev ( 2021-11-05 15:24:12 +0200 )edit

2 Answers

Sort by » oldest newest most voted
1

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

tmonteil gravatar image

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 more

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 gravatar imageKatoptriss ( 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.

Max Alekseyev gravatar imageMax Alekseyev ( 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.

Katoptriss gravatar imageKatoptriss ( 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?

Max Alekseyev gravatar imageMax Alekseyev ( 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.

Katoptriss gravatar imageKatoptriss ( 2021-11-05 23:26:03 +0200 )edit
0

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

Max Alekseyev gravatar image

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

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 more

Comments

Perfect, thank you very much for all your help!

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

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

Max Alekseyev gravatar imageMax Alekseyev ( 2021-11-06 22:37:18 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-11-04 22:37:30 +0200

Seen: 188 times

Last updated: Nov 06 '21