#32312 closed enhancement (fixed)

faster abelian_group() method for elliptic curves over finite fields

Reported by: Lorenz Panny Owned by:
Priority: major Milestone: sage-9.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:

Status badges

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 order n₁; we will extend P to a basis (P,Q') where Q' has order n₂ = #E/n₁.
  • Remove all unneeded prime factors from the order of Q, i.e., multiply by the part of n₁ that's coprime to n₂.
  • Find an appropriate multiple [x]P such that Q' := Q-[x]P has order n₂; this involves a (typically easy) discrete-logarithm 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**e-1)**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**e-1)**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 polynomial-time (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 Lorenz Panny

Status: newneeds_review

comment:2 Changed 14 months ago by Frédéric Chapoton

Cc: John Cremona added

comment:3 Changed 14 months ago by Kwankyu Lee

Cc: Kwankyu Lee added

comment:4 Changed 14 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:5 Changed 14 months ago by Lorenz Panny

Priority: minormajor

comment:6 Changed 14 months ago by Lorenz Panny

Cc: Luca De Feo added

comment:7 Changed 14 months ago by Travis Scrimshaw

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?

assert len(gens) <= 2

Also, it would be better to write this on two lines:

-S, T = n//nQ * P, n2 * Q
+S = n//nQ * P
+T = n2 * Q

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?

comment:8 Changed 14 months ago by git

Commit: a2802976db135e8e2d87dbd825049624b1bb6c3da56d7ce9f21856fbc1fbdbd7af71163463a34ede

Branch pushed to git repo; I updated commit sha1. New commits:

a56d7ceincorporate feedback from #32312

comment:9 Changed 14 months ago by Lorenz Panny

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 generic-group 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 git

Commit: a56d7ce9f21856fbc1fbdbd7af71163463a34edec90f367923bacf046c5c02fb15390e7cba0d10b5

Branch pushed to git repo; I updated commit sha1. New commits:

c90f367the output is just the abelian group object (and has been for a while)

comment:11 in reply to:  9 ; Changed 14 months ago by Travis Scrimshaw

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) <= 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.

That was my understanding from looking at the previous code, but I figured I should double-check.

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 generic-group 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 git

Commit: c90f367923bacf046c5c02fb15390e7cba0d10b584bfc08982d2fc1a8327fdcbdec112ce6fa85390

Branch pushed to git repo; I updated commit sha1. New commits:

84bfc08improve documentation

comment:13 in reply to:  11 Changed 14 months ago by Lorenz Panny

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:14 Changed 14 months ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Thank you. LGTM.

comment:15 Changed 13 months ago by Volker Braun

Branch: public/optimize_elliptic_curve_group_structure_computation84bfc08982d2fc1a8327fdcbdec112ce6fa85390
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.