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: sage-8.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 jdemeyer)

We can compute the generators of the group of F_q-points much faster than we can compute the full group structure.

Attachments (1)

ellgroup.patch (2.2 KB) - added by jdemeyer 5 years ago.

Download all attachments as: .zip

Change History (39)

Changed 5 years ago by jdemeyer

comment:1 Changed 3 years ago by cremona

What improvement do you have in mind?

comment:2 Changed 3 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-6.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 jdemeyer

  • Branch set to u/jdemeyer/improve_abelian_group___for_elliptic_curves_over_a_finite_field

comment:4 Changed 3 years ago by jdemeyer

  • Commit set to 46393f34e5bf179dfc79a4fa597838ef18910981
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

46393f3Implement elliptic curve gens() using PARI

comment:5 follow-up: Changed 3 years ago by cremona

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 d1|d1, 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 follow-ups: Changed 3 years ago by cremona

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 jdemeyer

Replying to cremona:

Perhaps this ticket should be dependent on #16931, which is referred to in comments in the code?

I could do that, but does it really matter that much if #16931 depends on this one or the other way around?

comment:8 Changed 3 years ago by git

  • Commit changed from 46393f34e5bf179dfc79a4fa597838ef18910981 to f79f254b31cc32897b69ceb143c4be1d8c7a5bf4

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

f79f254k is not used

comment:9 in reply to: ↑ 5 Changed 3 years ago by jdemeyer

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 jdemeyer

  • Status changed from needs_review to needs_work

comment:11 Changed 3 years ago by jdemeyer

  • Dependencies set to #19808

comment:12 Changed 3 years ago by jdemeyer

  • Dependencies #19808 deleted
  • Milestone changed from sage-6.10 to sage-7.4

comment:13 Changed 3 years ago by git

  • Commit changed from f79f254b31cc32897b69ceb143c4be1d8c7a5bf4 to 30791f7f0e7c5cde66fa30e30e22bb588fb4bf9a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

30791f7Implement elliptic curve gens() using PARI

comment:14 Changed 3 years ago by git

  • Commit changed from 30791f7f0e7c5cde66fa30e30e22bb588fb4bf9a to 9e6e6b51b8b8fd3077ae40b455be55f0da842eae

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

9e6e6b5Further fixes to abelian_group() and gens()

comment:15 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:16 Changed 2 years ago by jpflori

  • Cc jpflori added

comment:17 Changed 2 years ago by jpflori

As the cardinality is computed here, shouldn't we take the opportunity to store it?

comment:18 Changed 2 years ago by cremona

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 chapoton

  • Status changed from needs_review to needs_work

failing doctests, probably random ?

comment:20 Changed 2 years ago by chapoton

  • Cc cremona added
  • Milestone changed from sage-7.4 to sage-8.0

needs work, because of deprecated _pari_

comment:21 Changed 21 months ago by klui

  • 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 klui

  • 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:

307c693Implement elliptic curve gens() using PARI
bfbcfaeFurther fixes to abelian_group() and gens()
cbfecf6switched _pari_ to __pari__

comment:23 Changed 21 months ago by git

  • Commit changed from cbfecf6d8b1a60f16b1db5dcfc58a9f6e590448c to ef54049cdc05b636f6cdbbf467b9a02610697ab4

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

ef54049fixed doctests failing due to randomness of generators

comment:24 Changed 21 months ago by klui

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 git

  • Commit changed from ef54049cdc05b636f6cdbbf467b9a02610697ab4 to d08e42735558a776bdb05cd5a73844b7ca692b15

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

d08e427use additive group instead of multiplicative group for elliptic curve caching

comment:26 Changed 21 months ago by klui

David Roe is awesome. He figured out the bug.

I think all doctests should pass now.

comment:27 Changed 21 months ago by klui

  • 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 klui

  • Keywords elliptic curves sd87 added

comment:29 Changed 21 months ago by cremona

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 cremona

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 git

  • Commit changed from d08e42735558a776bdb05cd5a73844b7ca692b15 to fb5a253a45a36bab57647ba1934ec28b505aa6ae

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

fb5a253added cremona's suggestion to the docstring

comment:32 Changed 21 months ago by klui

I added your suggestion. I didn't see where AUTHORS was changed.

comment:33 Changed 21 months ago by cremona

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 cremona

  • Status changed from needs_review to positive_review

comment:35 Changed 21 months ago by gpark

  • Reviewers set to GaYee Park

All test passed.

comment:36 Changed 21 months ago by jpflori

  • Authors changed from Jeroen Demeyer to Jeroen Demeyer, Kevin Lui
  • Reviewers changed from GaYee Park to GaYee Park, John Cremona

comment:37 Changed 21 months ago by cremona

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 vbraun

  • 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
Note: See TracTickets for help on using tickets.