summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJeroen Demeyer <jdemeyer@cage.ugent.be>2016-09-02 11:08:12 +0200
committerJeroen Demeyer <jdemeyer@cage.ugent.be>2016-09-02 11:38:26 +0200
commitbdce5dced1e9f811616836253c4e7cd45b71fcf3 (patch)
treea50ee9f2a97d8b509c97755903d8754aa561a66e
parentWorkaround to prevent this calculation to blow the stack (diff)
Optimize Psi2()u/jdemeyer/psi2
-rw-r--r--src/sage/schemes/elliptic_curves/isogeny_small_degree.py45
1 files changed, 27 insertions, 18 deletions
diff --git a/src/sage/schemes/elliptic_curves/isogeny_small_degree.py b/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
index 3c22008..3840dea 100644
--- a/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
+++ b/src/sage/schemes/elliptic_curves/isogeny_small_degree.py
@@ -1455,23 +1455,30 @@ def Psi2(l):
The generic `l`-kernel polynomial.
- TESTS::
+ EXAMPLES::
sage: from sage.schemes.elliptic_curves.isogeny_small_degree import Psi2
sage: Psi2(11)
x^5 - 55*x^4*u + 994*x^3*u^2 - 8774*x^2*u^3 + 41453*x*u^4 - 928945/11*u^5 + 33*x^4 + 276*x^3*u - 7794*x^2*u^2 + 4452*x*u^3 + 1319331/11*u^4 + 216*x^3*v - 4536*x^2*u*v + 31752*x*u^2*v - 842616/11*u^3*v + 162*x^3 + 38718*x^2*u - 610578*x*u^2 + 33434694/11*u^3 - 4536*x^2*v + 73872*x*u*v - 2745576/11*u^2*v - 16470*x^2 + 580068*x*u - 67821354/11*u^2 - 185976*x*v + 14143896/11*u*v + 7533*x - 20437029/11*u - 12389112/11*v + 19964151/11
+ sage: Psi2(71) # long time (1 second)
+ -2209380711722505179506258739515288584116147237393815266468076436521/71*u^210 + ... - 14790739586438315394567393301990769678157425619440464678252277649/71
- """
- if not l in hyperelliptic_primes:
- raise ValueError("%s must be one of %s."%(l,hyperelliptic_primes))
+ TESTS::
+ sage: Psi2(13)
+ Traceback (most recent call last):
+ ...
+ ValueError: 13 must be one of [11, 17, 19, 23, 29, 31, 41, 47, 59, 71].
+ """
data = _hyperelliptic_isogeny_data(l)
- R = PolynomialRing(QQ,['x','u'])
- x, u = R.gens()
- L = PolynomialRing(R,'y')
- y = L.gen()
- K = R.extension(y**2-R(data['hyper_poly']),name = 'v')
+
+ R = PolynomialRing(QQ, 'u')
+ u = R.gen()
+ L = PolynomialRing(R, 'v')
+ v = L.gen()
+ K = R.extension(v*v - R(data['hyper_poly']), 'v')
v = K.gen()
+
from sage.categories.homset import Hom
h = Hom(K,K)(-v)
@@ -1482,19 +1489,21 @@ def Psi2(l):
s1 = K(data['A2'])
d = (l-1)//2
- s = [1]
- t = [d,s1,((1-10*d)*A - Abar)*(1/QQ(30))]
- t += [((1-28*d)*B - 42*t[1]*A - Bbar)*(1/QQ(70))]
- c = [0,6*t[2] + 2*A*t[0],10*t[3] + 6*A*t[1] + 4*B*t[0]]
+ s = [K(1)]
+ t = [d, s1, ((1-10*d)*A - Abar) * QQ((1,30))]
+ t.append(((1-28*d)*B - 42*t[1]*A - Bbar) * QQ((1,70)))
+ c = [0, 6*t[2] + 2*A*t[0], 10*t[3] + 6*A*t[1] + 4*B*t[0]]
for n in range(2,d):
k = sum(c[i]*c[n-i] for i in range(1,n))
- c += [(3*k-(2*n-1)*(n-1)*A*c[n-1]-(2*n-2)*(n-2)*B*c[n-2])*(1/QQ((n-1)*(2*n+5)))]
+ c.append((3*k-(2*n-1)*(n-1)*A*c[n-1]-(2*n-2)*(n-2)*B*c[n-2]) * QQ((1,(2*n+5)*(n-1))))
for n in range(3,d):
- t += [(c[n]-(4*n-2)*A*t[n-1]-(4*n-4)*B*t[n-2])*(1/QQ(4*n+2))]
+ t.append((c[n]-(4*n-2)*A*t[n-1]-(4*n-4)*B*t[n-2]) * QQ((1,4*n+2)))
for n in range(1,d+1):
- s += [(-1/QQ(n))*sum((-1)**i*t[i]*s[n-i] for i in range(1,n+1))]
- R = PolynomialRing(QQ,['x','u','v'])
- return sum(R((-1)**i*s[i]*x**(d-i)) for i in range(0,d+1))
+ s.append(QQ((-1,n)) * sum((-1)**i*t[i]*s[n-i] for i in range(1,n+1)))
+
+ R = PolynomialRing(QQ, ('x', 'u', 'v'))
+ x = R.gen(0)
+ return sum((-1)**i * x**(d-i) * R(s[i].lift()) for i in range(0,d+1))
def isogenies_prime_degree_genus_plus_0(E, l=None):