Opened 5 years ago

Closed 2 years ago

# Improve gens() for elliptic curves over a finite field

Reported by: Owned by: jdemeyer major sage-8.0 elliptic curves elliptic curves, sd87 jpflori, cremona Jeroen Demeyer, Kevin Lui GaYee Park, John Cremona N/A fb5a253 (Commits) fb5a253a45a36bab57647ba1934ec28b505aa6ae

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

### comment:1 Changed 4 years ago by cremona

What improvement do you have in mind?

### comment:2 Changed 4 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 4 years ago by jdemeyer

• Branch set to u/jdemeyer/improve_abelian_group___for_elliptic_curves_over_a_finite_field

### comment:4 Changed 4 years ago by jdemeyer

• 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 follow-up: ↓ 9 Changed 4 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: ↓ 7 ↓ 10 Changed 4 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 4 years ago by jdemeyer

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 4 years ago by git

• 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 4 years ago by jdemeyer

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 4 years ago by jdemeyer

• Status changed from needs_review to needs_work

### comment:11 Changed 4 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:

 ​30791f7 `Implement 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:

 ​9e6e6b5 `Further fixes to abelian_group() and gens()`

### comment:15 Changed 3 years ago by jdemeyer

• Status changed from needs_work to needs_review

### comment:17 Changed 3 years ago by jpflori

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

### comment:18 Changed 3 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 3 years ago by chapoton

• Status changed from needs_review to needs_work

failing doctests, probably random ?

### comment:20 Changed 2 years ago by chapoton

• Milestone changed from sage-7.4 to sage-8.0

needs work, because of deprecated `_pari_`

### comment:21 Changed 2 years 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 2 years 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:

 ​307c693 `Implement elliptic curve gens() using PARI` ​bfbcfae `Further fixes to abelian_group() and gens()` ​cbfecf6 `switched _pari_ to __pari__`

### comment:23 Changed 2 years ago by git

• 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 2 years 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 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 2 years ago by git

• 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 2 years ago by klui

David Roe is awesome. He figured out the bug.

I think all doctests should pass now.

### comment:27 Changed 2 years 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 2 years ago by klui

• Keywords elliptic curves sd87 added

### comment:29 Changed 2 years 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 2 years 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 2 years ago by git

• 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:33 Changed 2 years 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 2 years ago by cremona

• Status changed from needs_review to positive_review

### comment:35 Changed 2 years ago by gpark

• Reviewers set to GaYee Park

All test passed.

### comment:36 Changed 2 years 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 2 years 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 2 years 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.