ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 09 Aug 2018 18:42:18 -0500Efficient n-th division polynomial of elliptic curvehttp://ask.sagemath.org/question/41280/efficient-n-th-division-polynomial-of-elliptic-curve/I try to implement the algorithm described in sec. 4 of this paper: https:// eprint.iacr.org/2002/109.pdf. Currently I have the following code:
N = 1444329727510154393553799612747635457542181563961160832013134005088873165794135221
js = [(-2^5)^3, (-2^5*3)^3, (-2^5*3*5*11)^3, (-2^6*3*5*23*29)^3]
R = Integers(N)
B1 = B2 = 10
for j in js:
a = R(j)/(R(1728)-R(j))
cs = [random.randint(1,N) for _ in range(B1)]
xs = [random.randint(1,N) for _ in range(B2)]
for c in cs:
E = EllipticCurve([3*a*c^2, 2*a*c^3])
F = E.division_polynomial(N)
for x in xs:
z = F(x)
if gcd(z,N) != 1:
print(j, c, x, z, gcd(z,N))
I think it is correct, but the division polynomial computation runs forever, while the paper claims it finishes in seconds because every operation is modulo some integer (sec. 3). It also uses dynamical programming and I don't know how division_polynomial is implemented.
How can I do this more efficiently in Sage?polybiusTue, 27 Feb 2018 05:59:26 -0600http://ask.sagemath.org/question/41280/generating the ring for schoof's division polynomialshttp://ask.sagemath.org/question/43301/generating-the-ring-for-schoofs-division-polynomials/ hello,
i want to generate the ring $F_p[x,y]/(y^2-x^3-ax-b)$, which is necessary to compute the division polynomials in schoof's algorithm to compute the amount of elements of a elliptic curve of the form $y^2=x^3+ax+b$ over $F_p$.
I already tried this:
R.<x,y>=PolynomialRing(Zmod(p))
F=R.quo(y^2-x^3-ax-b)
x,y=F.gens()
When i computed some division polynomials in the generated F and matched them with division polynomials which sage computed by this:
F=Zmod(p)
E=EllipticCurve(F,[a,b])
E.division_polynomial()
i saw that my computed division polynomials must be wrong. Does anyone have an idea for generating the Ring $F_p[x,y]/(y^2-x^3-ax-b)$ or generating a "pseudo" elliptic curve in sage, because this code
F=Zmod(p)
E=EllipticCurve(F,[a,b])
E.division_polynomial()
doesn't work if $p$ isn't prime of course.
gebertlukiThu, 09 Aug 2018 18:42:18 -0500http://ask.sagemath.org/question/43301/Polynomial Long Division with Variable Coefficientshttp://ask.sagemath.org/question/38187/polynomial-long-division-with-variable-coefficients/I want to divide the following polynomial (in terms of $t$) with coefficients in terms of $\lambda$.
$$(\lambda^6 - 5\lambda^4 + 6\lambda^2 - 1)t^5 + (\lambda^5 - 4\lambda^3 + 3\lambda^2)t^6$$
by $$ \lambda t^2 -\lambda^2 t + \lambda$$
The resulting quotient will include a fractional component (the numerator's
degree will be strictly less than the denominator's degree).
This is what a quotient and remainder, added together, might look like:
$$ t(\frac{2\lambda^8 - 9 \lambda^6 + 2 \lambda^5 + 6 \lambda^4 - 4\lambda^2}{\lambda}) + t^3(\frac{2\lambda^6 - 9\lambda^4 + 3\lambda^3 + 6\lambda^2 -1 }{\lambda}) + \frac{t(\lambda^4 - 2\lambda) + (\lambda^3 - 4\lambda^2)}{\lambda t^2 - \lambda^2 t + \lambda}$$
*I have tried the following thus far* Any suggestions? The code below "does not work", because it outputs a quotient whose degree is greater than the degree of the dividend. Here $y$ takes the place of $\lambda$
and $x$ takes the place of $t$.
The quotient is:
-2*x^8 - x^4*y^4 + 2.0*x^6 - 3.0*x^5 - 1.0*x^4 - (2*x^5 + x^3)*y^3 + (-2*x^6 + 2.0*x^4 - x^2)*y^2 + (-2*x^7 +
4.0*x^5 + 1.0*x^3 - x)*y - 1
The remainder is:
-x^5 + (2*x^10 + 3.0*x^7 - 1.0*x^6 + 3.0*x^5 + 1.0*x^4 + x^2 + 1)*y
The code:
from sympy import Function, rsolve_poly, Symbol, rsolve, rsolve_hyper, oo
from sympy.abc import n
x = var('x')
y = var('y')
P.<x,y> = PolynomialRing(CC)
f = (y**5 - 4*y**3 + 3*y**2)*x**6 + (y**6 - 5*y**4 + 6*y**2 - 1)*x**5
g = y*x**2 - y**2*x + y
def division(dividend, divisor):
return (dividend._maxima_().divide(divisor).sage())
a = division(f,g)
print("The quotient is: \n")
print(a[0])
print("The remainder is: \n")
print(a[1])MunoThu, 06 Jul 2017 00:12:28 -0500http://ask.sagemath.org/question/38187/Division algorithm in a polynomial ring with variable coefficientshttp://ask.sagemath.org/question/37098/division-algorithm-in-a-polynomial-ring-with-variable-coefficients/ I am working on an algorithm to divide a polynomial `f` by a list of polynomials `[g1, g2, ..., gm]`. The following is my algorithm:
def div(f,g): # Division algorithm on Page 11 of Using AG by Cox;
# f is the dividend;
# g is a list of ordered divisors;
# The output consists of a list of coefficients for g and the remainder;
# p is the intermediate dividend;
n = len(g)
p, r, q = f, 0, [0 for x in range(0,n)]
while p != 0:
i, divisionoccured = 0, False
print(p,r,q);
while i < n and divisionoccured == False:
if g[i].lt().divides(p.lt()):
q[i] = q[i] + p.lt()//g[i].lt()
p = p - (p.lt()//g[i].lt())*g[i]
divisionoccured = True
else:
i = i + 1
if divisionoccured == False:
r = r + p.lt()
p = p - p.lt()
return q, r
Here is an example of implementing the algorithm:
K.<a,b> = FractionField(PolynomialRing(QQ,'a, b'))
P.<x,y,z> = PolynomialRing(K,order='lex')
f=a*x^2*y^3+x*y+2*b
g1=a^2*x+2
g2=x*y-b
div(f,[g1,g2])
Here is the result:
(a*x^2*y^3 + x*y + 2*b, 0, [0, 0])
(((-2)/a)*x*y^3 + x*y + 2*b, 0, [1/a*x*y^3, 0])
(x*y + 4/a^3*y^3 + 2*b, 0, [1/a*x*y^3 + ((-2)/a^3)*y^3, 0])
(4/a^3*y^3 + ((-2)/a^2)*y + 2*b, 0, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
(((-2)/a^2)*y + 2*b, 4/a^3*y^3, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
(2*b, 4/a^3*y^3 + ((-2)/a^2)*y, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
Error in lines 6-6
Traceback (most recent call last):
and some other error messages.
We can see that it worked well until the leading term is `2b`. it does not recognize the `2b` as a term. I tried:
(x).lt().divides(1)
It gives the answer `False`. But I tried
(x).lt().divides(a)
It gives error message. Is there a way to solve this? Thank you for your help!
KittyLMon, 27 Mar 2017 14:26:48 -0500http://ask.sagemath.org/question/37098/cyclic algebrashttp://ask.sagemath.org/question/33592/cyclic-algebras/I'm new to sage so forgive me if this is trivial. I want to eventually make a symbol algebras and generic crossed products. The first step would be to make quaternion algebras. I know there is a quaternion algebra function but I want to make one with generators and relations. When I try
F.<i,j> = FreeAlgebra(QQ,2)
A = F.g_algebra({i**2 :-1,j**2:-1,j*i:-i*j})
I get the follow error 'AssertionError: -1'
When I try
F.<i,j> = FreeAlgebra(QQ,2)
A = F.g_algebra({i**2 :-F(1),j**2:-F(1),j*i:-i*j})
I get the error 'ValueError: need more than 1 value to unpack'. Can anyone advise? I want to make the algebra $A=\mathbb{Q}[x,y|x^{n}=a,y^{n}=b,yx =\rho xy]$. If there is a better way to go about it then what I'm doing I would love to hear about that as well. Thanks. thenumber23Mon, 30 May 2016 19:13:52 -0500http://ask.sagemath.org/question/33592/Division polynomials just a function of x !http://ask.sagemath.org/question/34794/division-polynomials-just-a-function-of-x/ I evaluated Divison polynomials using
R.<A,B>=PolynomialRing(ZZ)
E = EllipticCurve([A,B])
g = E.division_polynomial(k)
The results i noticed were just function of $x$ , In theory i saw that division polynomials for k even depends on y. In there something I am unable to notice.
For example : ` E.division_polynomial(k)` returned `4*x^3 + 4*A*x + 4*B ` but theory says it is `2y`.
From this one can get a intuition that may be we are squaring them.
But ` E.division_polynomial(8)` returned a degree $33$ polynomial which means that clearly we are not squaring things.vishbSun, 11 Sep 2016 01:13:41 -0500http://ask.sagemath.org/question/34794/How to implement the multivariable division algorithm without passing to Grobner bases?http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/ Hi,
I'm new to Sage, and I'm wondering how to implement the multivariable division algorithm in Sage. I pulled up the "Multivariate Polynomials via libSINGULAR" page of the Sage Reference Manual v7.1, but it wasn't helpful.
What I'm wanting is a generalization of the quo_rem command that can take in more than one argument on the right and follows the division algorithm with respect to a fixed monomial ordering and the order that the polynomials are entered in.
Is there any set of commands that does that for me? If so, would you please include the code, say for the following example?
> Divide the polynomial y*x^2 + x*y^2 +
> y^2 by xy-1 and y2 -1 (in that order)
> using the lexicographic ordering with
> x>y. I would like to process more
> complicated examples, perhaps with
> that order and dividing by 8 things at
> once rather than 2.
I've learned about the p.mod(I) and p.reduce(I) commands where p is a polynomial and I is an ideal. The problem with those is that they seem to pass to a Grobner basis for I to get a "canonical" remainder rather than the remainder we'd get from the given order of the polynomials, as I tested switching the order of the polynomials in defining an ideal I and it did not change my answer for p.mod(I) or p.reduce(I).
Thanks!rmg512Thu, 31 Mar 2016 14:00:13 -0500http://ask.sagemath.org/question/32932/Bezout coefficients for Polynomialshttp://ask.sagemath.org/question/26955/bezout-coefficients-for-polynomials/ I want to find the bezout coefficient for those 2 polynomials :
f = 1+x-x^2-x^4+x^5 and g = -1+x^2+x^3-x^6
when I use the gcd function in sage the output is :
sage: gcd(f,g)
sage: 1
but when I use xgcd(f,g) it gives me the following :
(-27, 9*x^5 - 18*x^2 - 9*x - 9, 9*x^4 - 9*x^3 - 18*x + 18)
I want xgcd to give me 1 instead of -27 so the polynomials will be the bezout coefficients
P.S: I can't divide the polynomials by -27 because i'm working in ZZhashiramaWed, 27 May 2015 12:08:47 -0500http://ask.sagemath.org/question/26955/Groebner basis computation with symbolic constantshttp://ask.sagemath.org/question/26748/groebner-basis-computation-with-symbolic-constants/Hello! If I have a system of polynomials in $CC[x, y, z]$ or any other field, is there a way to create constants that are in that field in a way that makes Groebner basis computation still work? For example, if I want to compute the Groebner basis for the ideal generated by
y^2 + z - c1
x*y^2 - c2 - 2
Is there a way to indicate that the $c1$ and $c2$ are in $CC$ or whatever field I'm in? I've figured out how to get them to not be indeterminates (over the symbolic ring),
Ideal (y^2 + z - c1, x*y^2 - c2 - 2) of Multivariate Polynomial Ring in x, y, z over Symbolic Ring
but then the polynomials containing them don't have division.
AttributeError: 'MPolynomialRing_polydict_with_category' object has no attribute 'monomial_divides'
Thank you!jooyousWed, 06 May 2015 14:56:22 -0500http://ask.sagemath.org/question/26748/why division_polynomial results different with WIKI defineshttp://ask.sagemath.org/question/24719/why-division_polynomial-results-different-with-wiki-defines/
E = EllipticCurve(QQ,[0,0,1,-1,1]);E;E.short_weierstrass_model();E.division_polynomial(1);E.division_polynomial(2);E.division_polynomial(3);E.division_polynomial(4)
Elliptic Curve defined by y^2 + y = x^3 - x + 1 over Rational Field
Elliptic Curve defined by y^2 = x^3 - 16*x + 80 over Rational Field
1
4*x^3 - 4*x + 5
3*x^4 - 6*x^2 + 15*x - 1
8*x^9 - 48*x^7 + 210*x^6 - 210*x^4 + 198*x^3 - 90*x^2 + 142*x - 115
division_polynomial,2th=2*y=2*(x^3 - 16*x + 80)?
from wiki http://en.wikipedia.org/wiki/Division_polynomialscjshFri, 31 Oct 2014 00:45:43 -0500http://ask.sagemath.org/question/24719/