I'm dealing with elliptic curves in SAGE. Say the elliptic curve I have is y2=x3+x working over GF(43) and I have a polynomial expression in x and y: y2+xy+1. I want to be able to substitute y2=x3+x to get (x3+x)+xy+1. How do I do this?
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 y2−(x3+x) will amount to substituting y2=x3+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 + 1Here you could also choose e.g. R.<y,x> = PolynomialRing(GF(43), order='lex').
This works in this example, however I am also dealing with expressions of the form p(x)y2+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
If your polynomial is assumed to be zero, then it is also possible to entirely eliminate y by computing resultant of your polynomial and y2−(x3+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 + 1Asked: 3 years ago
Seen: 376 times
Last updated: Sep 25 '21
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
n is missing in polyomial