Opened 10 months ago
Closed 10 months ago
#26677 closed defect (fixed)
rational_points for some elliptic curves fails
Reported by:  alexjbest  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  algebraic geometry  Keywords:  rational points, elliptic curves 
Cc:  raghukul01, bhutz  Merged in:  
Authors:  Alex J. Best  Reviewers:  Ben Hutz 
Report Upstream:  N/A  Work issues:  
Branch:  b6a6e97 (Commits)  Commit:  b6a6e9793ca6be1a9635bc8d5505d60970e81367 
Dependencies:  Stopgaps: 
Description (last modified by )
sage: E = EllipticCurve("11a1") sage: E.rational_points(bound=5)  AttributeError Traceback (most recent call last) <ipythoninput1892e6de8bab5> in <module>() > 1 E.rational_points("11a1") AttributeError: 'function' object has no attribute 'rational_points' sage: E = EllipticCurve("11a1") sage: E.rational_points(bound=5) Exception raised by child process with pid=90565: Traceback (most recent call last): File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/parallel/use_fork.py", line 177, in __call__ self._subprocess(f, dir, *v0) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/parallel/use_fork.py", line 302, in _subprocess value = f(*args, **kwds) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/projective/projective_rational_point.py", line 460, in parallel_function Xp = X.change_ring(GF(p)) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/ell_generic.py", line 1347, in change_ring return self.base_extend(R) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/ell_number_field.py", line 151, in base_extend E = super(EllipticCurve_number_field, self).base_extend(R) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/ell_generic.py", line 1329, in base_extend return constructor.EllipticCurve([R(a) for a in self.a_invariants()]) File "sage/structure/factory.pyx", line 369, in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2046) return self.get_object(version, key, kwds) File "sage/structure/factory.pyx", line 412, in sage.structure.factory.UniqueFactory.get_object (build/cythonized/sage/structure/factory.c:2422) obj = self.create_object(version, key, **extra_args) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/constructor.py", line 471, in create_object return EllipticCurve_finite_field(R, x) File "/Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/ell_generic.py", line 149, in __init__ raise ArithmeticError("invariants " + str(ainvs) + " define a singular curve") ArithmeticError: invariants (0, 10, 1, 1, 2) define a singular curve <SNIP> /Users/alex/sage/local/lib/python2.7/sitepackages/sage/schemes/generic/algebraic_scheme.pyc in rational_points(self, **kwds) 1828 return X.points(**kwds) # checks for proper bound done in points functions 1829 except TypeError: > 1830 raise TypeError("Unable to enumerate points over %s."%F) 1831 elif (self.base_ring() in NumberFields() or self.base_ring() == ZZ)\ 1832 and hasattr(F, 'precision'): TypeError: Unable to enumerate points over Rational Field. sage:
Miraculously this works for the curve that is currently doctested 37a
,
The issue is that elliptic curves don't like to be base changed to bad primes, however for the purposes of sieving this is fine. So elliptic curves need to be convinced they are just curves for the purposes of sieving for points.
Precisely
Curve(E).rational_points(bound=5)
works even when E.rational_points(bound=5)
does not. Not sure if a change should be made to elliptic curves (to have a special rational_points method, or to the generic sieving code to first change the input to a rather generic type of scheme. I like the former more as the latter causes friction if people want to add special methods that speed up base_change or whatever.
Change History (19)
comment:1 Changed 10 months ago by
 Description modified (diff)
comment:2 Changed 10 months ago by
comment:3 Changed 10 months ago by
 Branch set to u/alexjbest/ellipticrationalpts
comment:4 Changed 10 months ago by
 Commit set to d22933248279eb613b11a1ba8e77d527de037aaf
Ok I added a patch, let me know if anyone thinks of a better solution, or if this should be somewhere more generic that elliptic_curve_number_field (thats just the situation I care about where I believe rational points is most common).
New commits:
d229332  Add custom rational_points for elliptic curves

comment:5 Changed 10 months ago by
 Status changed from new to needs_review
comment:6 Changed 10 months ago by
 Work issues set to wait for patchbot results
comment:7 Changed 10 months ago by
I didn't pull the branch to test, but don't you need to coerce the points back to original elliptic curve before returning.
comment:8 Changed 10 months ago by
 Commit changed from d22933248279eb613b11a1ba8e77d527de037aaf to 92354caf0e78c671fe0c77bac36ad785e0626c3d
Branch pushed to git repo; I updated commit sha1. New commits:
92354ca  coerce results back onto the curve

comment:9 Changed 10 months ago by
Good point!
comment:10 Changed 10 months ago by
 Status changed from needs_review to needs_work
Actually this requires some more code as we need to allow
sage: E = EllipticCurve([1,0]) sage: E.rational_points(bound=2, F= QuadraticField(1))
which currently fails
comment:11 Changed 10 months ago by
 Commit changed from 92354caf0e78c671fe0c77bac36ad785e0626c3d to 92587ffb817d566e1f49657e2e1e4141cb021d3b
Branch pushed to git repo; I updated commit sha1. New commits:
92587ff  allow for different field to be specified

comment:12 Changed 10 months ago by
 Status changed from needs_work to needs_review
 Work issues changed from wait for patchbot results to wait for patchbot results again?
comment:13 Changed 10 months ago by
 Reviewers set to Ben Hutz
 Status changed from needs_review to needs_work
You need to get the keyword 'F' before it can be used.
Maybe change the last example to
sage: E = EllipticCurve([1,0]) sage: E.rational_points(F=QuadraticField(1))
so an error like this shows up.
comment:14 Changed 10 months ago by
 Commit changed from 92587ffb817d566e1f49657e2e1e4141cb021d3b to b6a6e9793ca6be1a9635bc8d5505d60970e81367
Branch pushed to git repo; I updated commit sha1. New commits:
c611533  Add custom rational_points for elliptic curves

ea5cdbf  coerce results back onto the curve

f173817  allow for different field to be specified

28e91ad  fix to getting field

b6a6e97  Merge branch 'u/alexjbest/ellipticrationalpts' of git://trac.sagemath.org/sage into ellipticrationalpts

comment:16 Changed 10 months ago by
I think this is fine now. If we can get an all tests pass on the patchbot, I'll mark it positive.
comment:17 Changed 10 months ago by
 Work issues wait for patchbot results again? deleted
comment:18 Changed 10 months ago by
 Status changed from needs_review to positive_review
ran the long tests on my machine. All passed.
comment:19 Changed 10 months ago by
 Branch changed from u/alexjbest/ellipticrationalpts to b6a6e9793ca6be1a9635bc8d5505d60970e81367
 Resolution set to fixed
 Status changed from positive_review to closed
As stated above, the problem is that the sieving method is not considering whether a prime could be bad. I also prefer the suggestion of elliptic curves having their own method; if for no other reason that the method could be significantly improved in the case of the elliptic curves. In the short term, the elliptic curve method could just call the current method as a generic 'curve' until a faster specialized algorithm is implemented.