Ask Your Question

Polynomial Substitution for only higher terms

asked 2021-09-23 20:41:09 +0200

RKnebel gravatar image

updated 2021-10-26 21:39:27 +0200

FrédéricC gravatar image

I'm dealing with elliptic curves in SAGE. Say the elliptic curve I have is $y^2=x^3+x$ working over GF(43) and I have a polynomial expression in x and y: $$y^2 + xy + 1.$$ I want to be able to substitute $y^2=x^3+x$ to get $(x^3+x)+xy+1$. How do I do this?

edit retag flag offensive close merge delete


n is missing in polyomial

ortollj gravatar imageortollj ( 2021-09-24 11:09:54 +0200 )edit

2 Answers

Sort by » oldest newest most voted

answered 2021-09-24 00:44:30 +0200

rburing gravatar image

What you can do is choose a monomial ordering on the polynomial ring such that $y$ is the largest variable, so that in the multivariate division algorithm computing the remainder after division by $y^2 - (x^3 + x)$ will amount to substituting $y^2 = x^3 + x$:

sage: R.<x,y> = PolynomialRing(GF(43), order='invlex')
sage: (y^2 + x*y + 1).reduce([y^2 - (x^3 + x)])
x*y + x^3 + x + 1

Here you could also choose e.g. R.<y,x> = PolynomialRing(GF(43), order='lex').

edit flag offensive delete link more


This works in this example, however I am also dealing with expressions of the form $p(x)y^2+ q(x)$ where $p,q$ are polynomials of large degree. Implementing the above does the opposite; it takes the large powers of $x$ and replaces them with $y$

RKnebel gravatar imageRKnebel ( 2021-10-05 18:08:03 +0200 )edit

answered 2021-09-24 19:24:48 +0200

Max Alekseyev gravatar image

updated 2021-09-25 20:48:09 +0200

If your polynomial is assumed to be zero, then it is also possible to entirely eliminate $y$ by computing resultant of your polynomial and $y^2-(x^3+x)$ with respect to $y$:

sage: R.<x,y> = PolynomialRing(GF(43))                                                                                                                                                                                 
sage: (y^2+x*y+1).resultant(y^2-(x^3+x),y)                                                                                                                                                                         
x^6 - x^5 + 2*x^4 + x^3 + x^2 + 2*x + 1
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


Asked: 2021-09-23 20:41:09 +0200

Seen: 229 times

Last updated: Sep 25 '21