Opened 4 years ago
Closed 4 years ago
#26677 closed defect (fixed)
rational_points for some elliptic curves fails
Reported by:  Alex J. Best  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  algebraic geometry  Keywords:  rational points, elliptic curves 
Cc:  Raghukul Raman, Ben Hutz  Merged in:  
Authors:  Alex J. Best  Reviewers:  Ben Hutz 
Report Upstream:  N/A  Work issues:  
Branch:  b6a6e97 (Commits, GitHub, GitLab)  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 4 years ago by
Description:  modified (diff) 

comment:2 Changed 4 years ago by
comment:3 Changed 4 years ago by
Branch:  → u/alexjbest/ellipticrationalpts 

comment:4 Changed 4 years ago by
Commit:  → 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 4 years ago by
Authors:  → Alex J. Best 

Status:  new → needs_review 
comment:6 Changed 4 years ago by
Work issues:  → wait for patchbot results 

comment:7 Changed 4 years 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 4 years ago by
Commit:  d22933248279eb613b11a1ba8e77d527de037aaf → 92354caf0e78c671fe0c77bac36ad785e0626c3d 

Branch pushed to git repo; I updated commit sha1. New commits:
92354ca  coerce results back onto the curve

comment:10 Changed 4 years ago by
Status:  needs_review → 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 4 years ago by
Commit:  92354caf0e78c671fe0c77bac36ad785e0626c3d → 92587ffb817d566e1f49657e2e1e4141cb021d3b 

Branch pushed to git repo; I updated commit sha1. New commits:
92587ff  allow for different field to be specified

comment:12 Changed 4 years ago by
Status:  needs_work → needs_review 

Work issues:  wait for patchbot results → wait for patchbot results again? 
comment:13 Changed 4 years ago by
Reviewers:  → Ben Hutz 

Status:  needs_review → 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 4 years ago by
Commit:  92587ffb817d566e1f49657e2e1e4141cb021d3b → 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 4 years 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 4 years ago by
Work issues:  wait for patchbot results again? 

comment:18 Changed 4 years ago by
Status:  needs_review → positive_review 

ran the long tests on my machine. All passed.
comment:19 Changed 4 years ago by
Branch:  u/alexjbest/ellipticrationalpts → b6a6e9793ca6be1a9635bc8d5505d60970e81367 

Resolution:  → fixed 
Status:  positive_review → 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.