Opened 5 years ago
Closed 21 months ago
#16949 closed enhancement (fixed)
Improve gens() for elliptic curves over a finite field
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  elliptic curves  Keywords:  elliptic curves, sd87 
Cc:  jpflori, cremona  Merged in:  
Authors:  Jeroen Demeyer, Kevin Lui  Reviewers:  GaYee Park, John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  fb5a253 (Commits)  Commit:  fb5a253a45a36bab57647ba1934ec28b505aa6ae 
Dependencies:  Stopgaps: 
Description (last modified by )
We can compute the generators of the group of F_q
points much faster than we can compute the full group structure.
Attachments (1)
Change History (39)
Changed 5 years ago by
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
 Description modified (diff)
 Milestone changed from sage6.4 to sage6.10
 Summary changed from Improve abelian_group() for elliptic curves over a finite field to Improve gens() for elliptic curves over a finite field
comment:3 Changed 3 years ago by
 Branch set to u/jdemeyer/improve_abelian_group___for_elliptic_curves_over_a_finite_field
comment:4 Changed 3 years ago by
 Commit set to 46393f34e5bf179dfc79a4fa597838ef18910981
 Description modified (diff)
 Status changed from new to needs_review
New commits:
46393f3  Implement elliptic curve gens() using PARI

comment:5 followup: ↓ 9 Changed 3 years ago by
I will trust you that there are cases where this is all that the users needs.
Can we add to the documentation more from the documentation of pari's ellgroup() function? As I understand that, if ellgroup()[2] has length 1 then the group is cyclic and this point does generate it; while if it has length 2 then the first point has order d1 = exponent, the structure is [d1,d2] with d2>1 and d1d1, and the Weil pairing between the points has order exactly d2 even though the second "generator" may have order not d2 (its order must then be a multiple of d2 and a divisor of d1).
As the pari doc says, this avoids the possibly expensive Weil pairing step.
I will be testing this shortly.
comment:6 followups: ↓ 7 ↓ 10 Changed 3 years ago by
Perhaps this ticket should be dependent on #16931, which is referred to in comments in the code?
I would like to see and Example where the product of the orders of the two generators is greater than the cardinality. But maybe since the gens returned are random, this cannot be tested deterministically. That is a pity, but we could have something like
sage: E = EllipticCurve(GF(41),[2,5]) sage: P,Q = E.gens() sage: P.order() 22 sage: Q.order() 22 sage: P.order()*Q.order(), E.cardinality() (484, 44)
More importantly: suppose that I had done this before calling E.gens():
sage: E.abelian_group() Additive abelian group isomorphic to Z/22 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 41 sage: E.abelian_group().gens() ((35 : 33 : 1), (10 : 0 : 1)) sage: P,Q = E.abelian_group().gens() sage: P.order(),Q.order() (22, 2)
i.e. I had done the hard work, but it was ignored. Surely the new faster E.gens() would be even faster in this case if it checked whether generators were already known?
comment:7 in reply to: ↑ 6 Changed 3 years ago by
comment:8 Changed 3 years ago by
 Commit changed from 46393f34e5bf179dfc79a4fa597838ef18910981 to f79f254b31cc32897b69ceb143c4be1d8c7a5bf4
Branch pushed to git repo; I updated commit sha1. New commits:
f79f254  k is not used

comment:9 in reply to: ↑ 5 Changed 3 years ago by
Replying to cremona:
As I understand that, if ellgroup()[2] has length 1 then the group is cyclic and this point does generate it; while if it has length 2 then the first point has order d1 = exponent
At least the above info is in the docstring. I also think this is the important part.
comment:10 in reply to: ↑ 6 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:11 Changed 3 years ago by
 Dependencies set to #19808
comment:12 Changed 3 years ago by
 Dependencies #19808 deleted
 Milestone changed from sage6.10 to sage7.4
comment:13 Changed 3 years ago by
 Commit changed from f79f254b31cc32897b69ceb143c4be1d8c7a5bf4 to 30791f7f0e7c5cde66fa30e30e22bb588fb4bf9a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
30791f7  Implement elliptic curve gens() using PARI

comment:14 Changed 3 years ago by
 Commit changed from 30791f7f0e7c5cde66fa30e30e22bb588fb4bf9a to 9e6e6b51b8b8fd3077ae40b455be55f0da842eae
Branch pushed to git repo; I updated commit sha1. New commits:
9e6e6b5  Further fixes to abelian_group() and gens()

comment:15 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:16 Changed 2 years ago by
 Cc jpflori added
comment:17 Changed 2 years ago by
As the cardinality is computed here, shouldn't we take the opportunity to store it?
comment:18 Changed 2 years ago by
Definitely yes. And when the cardinality is known and can be factored the abelian_group() method will work faster.
comment:19 Changed 2 years ago by
 Status changed from needs_review to needs_work
failing doctests, probably random ?
comment:20 Changed 2 years ago by
 Cc cremona added
 Milestone changed from sage7.4 to sage8.0
needs work, because of deprecated _pari_
comment:21 Changed 21 months ago by
 Branch changed from u/jdemeyer/improve_abelian_group___for_elliptic_curves_over_a_finite_field to u/klui/improve_abelian_group___for_elliptic_curves_over_a_finite_field
comment:22 Changed 21 months ago by
 Commit changed from 9e6e6b51b8b8fd3077ae40b455be55f0da842eae to cbfecf6d8b1a60f16b1db5dcfc58a9f6e590448c
I convert _pari_
to __pari__
which fixed some of the failing doctests.
The doctests for E.gens()
sometimes fails but I've verified that in those case, the outputs are still generators of the elliptic curve. I think it was mentioned earlier that the outputs are expected to be random. Is there a better way to do the doctest in L1248 and L1251 of ell_finite_field.py?
New commits:
307c693  Implement elliptic curve gens() using PARI

bfbcfae  Further fixes to abelian_group() and gens()

cbfecf6  switched _pari_ to __pari__

comment:23 Changed 21 months ago by
 Commit changed from cbfecf6d8b1a60f16b1db5dcfc58a9f6e590448c to ef54049cdc05b636f6cdbbf467b9a02610697ab4
Branch pushed to git repo; I updated commit sha1. New commits:
ef54049  fixed doctests failing due to randomness of generators

comment:24 Changed 21 months ago by
I still get this failure
sage t elliptic_curves/ell_finite_field.py ********************************************************************** File "elliptic_curves/ell_finite_field.py", line 1391, in sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field.abelian_group Failed example: E.abelian_group() Expected: Additive abelian group isomorphic to Z/10 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 11 Got: (Multiplicative Abelian group isomorphic to C10, ((3 : 4 : 1),)) ********************************************************************** 1 item had failures: 1 of 23 in sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field.abelian_group [306 tests, 1 failure, 3.44 s]
But when I manually compute the doctest, it gives the expected answer.
comment:25 Changed 21 months ago by
 Commit changed from ef54049cdc05b636f6cdbbf467b9a02610697ab4 to d08e42735558a776bdb05cd5a73844b7ca692b15
Branch pushed to git repo; I updated commit sha1. New commits:
d08e427  use additive group instead of multiplicative group for elliptic curve caching

comment:26 Changed 21 months ago by
David Roe is awesome. He figured out the bug.
I think all doctests should pass now.
comment:27 Changed 21 months ago by
 Status changed from needs_work to needs_review
I haven't actually read much of the code. I just fixed the failing doctests. Hopefully this is okay.
comment:28 Changed 21 months ago by
 Keywords elliptic curves sd87 added
comment:29 Changed 21 months ago by
This looks better: I looked at the code but have not had time for testing. I would prefer the docstring which now says "Unlike :meth:abelian_group
, this works even over large finite fields" to say "this works over larger finite fields where :meth:abelian_group
may be too expensive".
comment:30 Changed 21 months ago by
By the way I think the conventions is to add names to lists of AUTHORS but not delete them.
comment:31 Changed 21 months ago by
 Commit changed from d08e42735558a776bdb05cd5a73844b7ca692b15 to fb5a253a45a36bab57647ba1934ec28b505aa6ae
Branch pushed to git repo; I updated commit sha1. New commits:
fb5a253  added cremona's suggestion to the docstring

comment:32 Changed 21 months ago by
I added your suggestion. I didn't see where AUTHORS was changed.
comment:33 Changed 21 months ago by
Thanks. (In the diffs you can see
 AUTHORS: +  if the group is trivial: an empty tuple.   John Cremona +  if the group is cyclic: a tuple with 1 point, a generator. +
;)
comment:34 Changed 21 months ago by
 Status changed from needs_review to positive_review
comment:36 Changed 21 months ago by
 Reviewers changed from GaYee Park to GaYee Park, John Cremona
comment:37 Changed 21 months ago by
Thanks for adding me as referee. (Do we normally include as referees people who have not commented on the ticket as well? I don't know who gpark is, but assume there's a reason for them adding their name.)
comment:38 Changed 21 months ago by
 Branch changed from u/klui/improve_abelian_group___for_elliptic_curves_over_a_finite_field to fb5a253a45a36bab57647ba1934ec28b505aa6ae
 Resolution set to fixed
 Status changed from positive_review to closed
What improvement do you have in mind?