Opened 14 months ago
Closed 13 months ago
#32312 closed enhancement (fixed)
faster abelian_group() method for elliptic curves over finite fields
Reported by:  Lorenz Panny  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  elliptic curves  Keywords:  elliptic curves, group structure, finite field 
Cc:  John Cremona, Kwankyu Lee, Luca De Feo  Merged in:  
Authors:  Lorenz Panny  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  84bfc08 (Commits, GitHub, GitLab)  Commit:  84bfc08982d2fc1a8327fdcbdec112ce6fa85390 
Dependencies:  Stopgaps: 
Description
This patch improves the computation of a basis of the group of rational points for elliptic curves over finite fields.
The algorithm works as follows:
 Call
gens()
to obtain a generating set; this in turn calls into PARI which factors the group order and uses pairings to determine the group structure.  Let
P
denote the point of larger ordern₁
; we will extendP
to a basis(P,Q')
whereQ'
has ordern₂ = #E/n₁
.  Remove all unneeded prime factors from the order of
Q
, i.e., multiply by the part ofn₁
that's coprime ton₂
.  Find an appropriate multiple
[x]P
such thatQ' := Q[x]P
has ordern₂
; this involves a (typically easy) discretelogarithm computation.  As desired,
(P,Q')
is then a basis of the group of rational points of E.
Benchmarks: I ran .abelian_group()
on thousands of random elliptic curves over prime and extension fields with sizes between 8 and 160 bits using both Sage 9.3 and the new implementation, and the new algorithm was between 30% and 50% faster on average (for all sizes).
In addition, there are cases for which the new algorithm is dramatically faster. For example:
Sage 9.3:
sage: for e in [7,17,31,61,127]: ....: E = EllipticCurve(GF((2**e1)**2), [1,0]) ....: %time E.abelian_group() ....: CPU times: user 20.7 ms, sys: 66 µs, total: 20.7 ms Wall time: 20.8 ms Additive abelian group isomorphic to Z/128 + Z/128 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 127^2 CPU times: user 342 ms, sys: 45 µs, total: 342 ms Wall time: 342 ms Additive abelian group isomorphic to Z/131072 + Z/131072 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 131071^2 CPU times: user 1min 23s, sys: 103 ms, total: 1min 23s Wall time: 1min 23s Additive abelian group isomorphic to Z/2147483648 + Z/2147483648 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 2147483647^2 #### (continues to run for a long time, then dies from lack of memory)
New code:
sage: for e in [7,17,31,61,127]: ....: E = EllipticCurve(GF((2**e1)**2), [1,0]) ....: %time E.abelian_group() ....: CPU times: user 3.78 ms, sys: 0 ns, total: 3.78 ms Wall time: 3.78 ms Additive abelian group isomorphic to Z/128 + Z/128 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 127^2 CPU times: user 7.75 ms, sys: 0 ns, total: 7.75 ms Wall time: 7.77 ms Additive abelian group isomorphic to Z/131072 + Z/131072 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 131071^2 CPU times: user 12 ms, sys: 0 ns, total: 12 ms Wall time: 12 ms Additive abelian group isomorphic to Z/2147483648 + Z/2147483648 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 2147483647^2 CPU times: user 29.7 ms, sys: 0 ns, total: 29.7 ms Wall time: 29.8 ms Additive abelian group isomorphic to Z/2305843009213693952 + Z/2305843009213693952 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 2305843009213693951^2 CPU times: user 280 ms, sys: 0 ns, total: 280 ms Wall time: 280 ms Additive abelian group isomorphic to Z/170141183460469231731687303715884105728 + Z/170141183460469231731687303715884105728 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 170141183460469231731687303715884105727^2
The only curves for which the new algorithm is not polynomialtime (after factoring the order) are curves whose group of rational points has ℓ^∞
torsion isomorphic to ℤ/ℓ^r × ℤ/ℓ^s
where r > s > 0
for some prime ℓ
. In that case, the cost includes a factor Θ(√ℓ)
. I don't think I know how to construct such curves for large ℓ
.
Change History (15)
comment:1 Changed 14 months ago by
Status:  new → needs_review 

comment:2 Changed 14 months ago by
Cc:  John Cremona added 

comment:3 Changed 14 months ago by
Cc:  Kwankyu Lee added 

comment:4 Changed 14 months ago by
Milestone:  sage9.4 → sage9.5 

comment:5 Changed 14 months ago by
Priority:  minor → major 

comment:6 Changed 14 months ago by
Cc:  Luca De Feo added 

comment:7 Changed 14 months ago by
comment:8 Changed 14 months ago by
Commit:  a2802976db135e8e2d87dbd825049624b1bb6c3d → a56d7ce9f21856fbc1fbdbd7af71163463a34ede 

Branch pushed to git repo; I updated commit sha1. New commits:
a56d7ce  incorporate feedback from #32312

comment:9 followup: 11 Changed 14 months ago by
Replying to tscrim:
Is this something that is guaranteed to happen or is it for controlling user input?
assert len(gens) <= 2
This is guaranteed by the documentation and current implementation of self.gens()
. Unless someone changes the meaning of gens()
in a mathematically nonsensical way in the future, it will always hold. I suppose the assert
is realistically useless, but it does make explicit an assumption of the following code.
Do you have a reference for this algorithm you could add to the doc?
I pretty much made this one up while writing the code. Does anyone know a reference? This is a genericgroup algorithm, so it's probably a special case of something in Sutherland's thesis (or elsewhere), but the specifics here are tailored to the output of gens()
.
comment:10 Changed 14 months ago by
Commit:  a56d7ce9f21856fbc1fbdbd7af71163463a34ede → c90f367923bacf046c5c02fb15390e7cba0d10b5 

Branch pushed to git repo; I updated commit sha1. New commits:
c90f367  the output is just the abelian group object (and has been for a while)

comment:11 followup: 13 Changed 14 months ago by
Reviewers:  → Travis Scrimshaw 

Replying to lorenz:
Replying to tscrim:
Is this something that is guaranteed to happen or is it for controlling user input?
assert len(gens) <= 2This is guaranteed by the documentation and current implementation of
self.gens()
. Unless someone changes the meaning ofgens()
in a mathematically nonsensical way in the future, it will always hold. I suppose theassert
is realistically useless, but it does make explicit an assumption of the following code.
That was my understanding from looking at the previous code, but I figured I should doublecheck.
Do you have a reference for this algorithm you could add to the doc?
I pretty much made this one up while writing the code. Does anyone know a reference? This is a genericgroup algorithm, so it's probably a special case of something in Sutherland's thesis (or elsewhere), but the specifics here are tailored to the output of
gens()
.
This is outside of my area of expertise. Could you add a bit about the algorithm in to the documentation? Also, is this random still? It looks quite deterministic.
comment:12 Changed 14 months ago by
Commit:  c90f367923bacf046c5c02fb15390e7cba0d10b5 → 84bfc08982d2fc1a8327fdcbdec112ce6fa85390 

Branch pushed to git repo; I updated commit sha1. New commits:
84bfc08  improve documentation

comment:13 Changed 14 months ago by
Replying to tscrim:
Could you add a bit about the algorithm in to the documentation? Also, is this random still? It looks quite deterministic.
Done, and yes: It calls into .gens()
, which is randomized. I've tried making this a little bit clearer in the newest commit.
comment:15 Changed 13 months ago by
Branch:  public/optimize_elliptic_curve_group_structure_computation → 84bfc08982d2fc1a8327fdcbdec112ce6fa85390 

Resolution:  → fixed 
Status:  positive_review → closed 
I cannot attest to the validity of the algorithm, but it is implemented as defined as far as I can tell and it passes doctests.
Is this something that is guaranteed to happen or is it for controlling user input?
Also, it would be better to write this on two lines:
In the doc, you should use
\ZZ
instead of\mathbb Z
for uniformity.Do you have a reference for this algorithm you could add to the doc?