Opened 5 years ago

Closed 12 months ago

#16931 closed enhancement (fixed)

Elliptic curve point counting over F_q using PARI

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-8.4
Component: elliptic curves Keywords: sd87
Cc: pbruin, cremona, kedlaya, jpflori, defeo Merged in:
Authors: Jeroen Demeyer Reviewers: David Roe, John Cremona
Report Upstream: N/A Work issues:
Branch: 209e7d6 (Commits) Commit: 209e7d619854f31458df537125422378a5cb9a01
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

PARI now supports point counting over F_q instead of F_p. We should use this new functionality in Sage!

Change History (62)

comment:1 Changed 5 years ago by jdemeyer

  • Cc pbruin cremona added

comment:2 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:4 Changed 5 years ago by jdemeyer

  • Description modified (diff)

Never mind the timings, PARI does its own caching now...

comment:5 Changed 5 years ago by jdemeyer

  • Dependencies changed from #15767, #16927, #8373, #16930 to #15767, #16927, #8373, #16930, #16934

comment:6 Changed 5 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/16931
  • Created changed from 09/04/14 12:54:32 to 09/04/14 12:54:32
  • Modified changed from 09/07/14 21:31:47 to 09/07/14 21:31:47

comment:7 Changed 5 years ago by jdemeyer

  • Commit set to 51a753d5ec93fcd9c0228450eb6623827d4c97b1
  • Dependencies changed from #15767, #16927, #8373, #16930, #16934 to #15767, #16927, #8373, #16930, #16934, #16944

New commits:

8286a4cAdd ffprimroot, fflog, fforder
63ec17aAllow modulus="primitive" in finite field constructor
abcf8a6Deprecate non-polynomial modulus argument in constructor of implementations of finite fields
8cdbd79Improve computation of j-invariant over smaller field
8f805a2Trac 16934: always put finite field implementation in factory key
8923777Trac 16934: remove method FiniteFieldFactory.other_keys()
5e2681eTrac 16934: more cleaning up
ffb74faTrac 16934: add doctest
51a753dElliptic curve point counting over F_q using PARI

comment:8 Changed 5 years ago by jdemeyer

  • Dependencies changed from #15767, #16927, #8373, #16930, #16934, #16944 to #15767, #16927, #8373, #16930, #16934, #16944, #16946

comment:9 Changed 5 years ago by git

  • Commit changed from 51a753d5ec93fcd9c0228450eb6623827d4c97b1 to f05d8c11fa2c57015063ab8466d07fb09d54493e

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

9ff6d12Return FFELT in GF(q) -> PARI conversion
9335f76Add residue_field() method to polynomials over GF(p)
aeae7f9Merge branches 'ticket/16944' and 'ticket/16946' into HEAD
f05d8c1Elliptic curve point counting over F_q using PARI

comment:10 Changed 5 years ago by git

  • Commit changed from f05d8c11fa2c57015063ab8466d07fb09d54493e to 6a80f7f165f699d382a03b000d84ff4f35ef4d47

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

6a80f7fElliptic curve point counting over F_q using PARI

comment:11 Changed 5 years ago by jdemeyer

  • Dependencies changed from #15767, #16927, #8373, #16930, #16934, #16944, #16946 to #15767, #16927, #8373, #16930, #16934, #16944, #16946, #16947

comment:12 Changed 5 years ago by git

  • Commit changed from 6a80f7f165f699d382a03b000d84ff4f35ef4d47 to 4f9c038c5050535412649afb1fb19f473a280700

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

7c3274eUse pari_ffelt for residue fields
28ddd58Merge branches 'ticket/16944' and 'ticket/16947' into HEAD
4f9c038Elliptic curve point counting over F_q using PARI

comment:13 Changed 5 years ago by git

  • Commit changed from 4f9c038c5050535412649afb1fb19f473a280700 to 2049945d20f8e5561da7b1e80ece0255d43b3bdd

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

2049945Elliptic curve point counting over F_q using PARI

comment:14 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:15 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:16 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:17 Changed 5 years ago by jdemeyer

  • Description modified (diff)
  • Report Upstream changed from N/A to Reported upstream. Developers acknowledge bug.

comment:18 Changed 5 years ago by jdemeyer

  • Description modified (diff)
  • Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, but not in a stable release.

comment:19 Changed 4 years ago by jdemeyer

  • Dependencies changed from #15767, #16927, #8373, #16930, #16934, #16944, #16946, #16947 to #16949
  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-6.11
  • Summary changed from Elliptic curve point counting over F_q using new PARI to Elliptic curve point counting over F_q using PARI

comment:20 Changed 4 years ago by git

  • Commit changed from 2049945d20f8e5561da7b1e80ece0255d43b3bdd to d760c63324cf7f0b4f6656455ad5a044f43a5200

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

46393f3Implement elliptic curve gens() using PARI
d760c63Elliptic curve point counting over F_q using PARI

comment:21 Changed 4 years ago by git

  • Commit changed from d760c63324cf7f0b4f6656455ad5a044f43a5200 to 7e93e62ea717e4391ec2ae441ec161ff88f3fd2c

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

7e93e62Elliptic curve point counting over F_q using PARI

comment:22 Changed 4 years ago by jdemeyer

  • Status changed from new to needs_review

comment:23 follow-up: Changed 4 years ago by cremona

Thanks for your work on this. First two few small points:

  1. In the documentation for ellcard(), we need to say that when self is defined over Q and p is a prime of bad reduction then the number returned is the size of the group of nonsingular points on the reduction (i.e. p-1, p+1 or p depending). I wondered about this, did some experiments, and then verified with the pari documentation.
  1. Why is ellorder() removed?

I think someone other than me should review this. There is a vast amount of code written by me being removed here, which is hard. Without going into the details of the pari implementation I would not want to agree to removing the special code for j=0 and j=1728 in characteristics 2 and 3. We had to do quite a lot of mathematics to get this right, which was not in the literature, and even the examples here are quite instructive.

Secondly, the old code was careful to only ever do counting over the field generated over the prime field by the j-invariant. From there is is quite easy to get the cardinality of any twist over any extension. Do you know that pari does that too? Try taking a curve over a small field, base-changing to an extension, applying a random twist, and then asking for the cardinality. With my code it swould take no longer than on the original. Is that still true?

I thought we had a convention for situations like this, that a Sage-only implementation could be kept and used if some parameter 'algorithm' was set? The parameter could be 'pari' by default.

comment:24 follow-up: Changed 4 years ago by jdemeyer

There is a vast amount of code written by me being removed here, which is hard.

For the record, I totally understand that. I had the same feeling when the PARI people implemented splitting field for polynomials over QQ which completely outperformed my implementation.

However, I consider it a "fact of life" that old code has to make place for new and better code.

I thought we had a convention for situations like this, that a Sage-only implementation could be kept and used if some parameter 'algorithm' was set? The parameter could be 'pari' by default.

I'm not really sure if that's a convention. Honestly, I don't really see the point of keeping the old code. I did keep all old doctests, which I think is important.

comment:25 in reply to: ↑ 24 ; follow-ups: Changed 4 years ago by cremona

Replying to jdemeyer:

There is a vast amount of code written by me being removed here, which is hard.

For the record, I totally understand that. I had the same feeling when the PARI people implemented splitting field for polynomials over QQ which completely outperformed my implementation.

I'm glad you know how this feels. Does Sage use the pari splitting field implementation now?

However, I consider it a "fact of life" that old code has to make place for new and better code.

Of course! There may be some benefit in keeping an independent implementation though, in case of bugs being found later.

I thought we had a convention for situations like this, that a Sage-only implementation could be kept and used if some parameter 'algorithm' was set? The parameter could be 'pari' by default.

I'm not really sure if that's a convention. Honestly, I don't really see the point of keeping the old code. I did keep all old doctests, which I think is important.

Agreed -- and looking more closely I see that you did move the tests for the special cases j=0, 1728 and not *re*move them. Thanks.

I will ask the pari-devs about the other points.

comment:26 in reply to: ↑ 25 Changed 4 years ago by jdemeyer

Replying to cremona:

I'm glad you know how this feels. Does Sage use the pari splitting field implementation now?

No, it doesn't. PARI only works with irreducible polynomials and I'm not sure if PARI works in the relative case (where the base field is a number field). My implementation is more general.

comment:27 in reply to: ↑ 25 Changed 4 years ago by jdemeyer

Replying to cremona:

looking more closely

git tip: do you know about the --patience option?

The default diff algorithm in git tries to minimize the number of changes. But this isn't really what you want, since it might match a random empty line from the old code with an unrelated empty line from the new code. With the --patience option, git uses a different algorithm which doesn't suffer from this: even though the diff will be larger, logical blocks will be kept together.

comment:28 Changed 4 years ago by kedlaya

  • Cc kedlaya added

comment:29 Changed 3 years ago by jpflori

  • Cc jpflori added

comment:30 Changed 3 years ago by kedlaya

  • Branch changed from u/jdemeyer/ticket/16931 to u/kedlaya/ticket/16931
  • Commit changed from 7e93e62ea717e4391ec2ae441ec161ff88f3fd2c to 2be66ca92ed226775dc5a2b92cb43657e20954c6

Merged with current develop branch (7.4beta0).


New commits:

46393f3Implement elliptic curve gens() using PARI
7e93e62Elliptic curve point counting over F_q using PARI
2be66caMerge branch 'u/jdemeyer/ticket/16931' into current develop (7.4beta0)

comment:31 Changed 3 years ago by kedlaya

I'm not sure I did this merge correctly. If not, we can switch back to jdemeyer's branch.

comment:32 Changed 3 years ago by jdemeyer

I think it's better to look at #16949 first anyway.

comment:33 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-7.0 to sage-7.4
  • Status changed from needs_review to needs_work

And in any case, adding 4499 lines to src/sage/libs/pari/gen.pyx cannot be right...

comment:34 Changed 3 years ago by jdemeyer

  • Branch changed from u/kedlaya/ticket/16931 to u/jdemeyer/ticket/16931

comment:35 Changed 3 years ago by git

  • Commit changed from 2be66ca92ed226775dc5a2b92cb43657e20954c6 to 78133cf80ce8d5265139ad704f43a66e2f144a36

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

9e6e6b5Further fixes to abelian_group() and gens()
78133cfElliptic curve point counting over F_q using PARI

comment:36 in reply to: ↑ 23 Changed 3 years ago by jdemeyer

Replying to cremona:

Secondly, the old code was careful to only ever do counting over the field generated over the prime field by the j-invariant. From there is is quite easy to get the cardinality of any twist over any extension. Do you know that pari does that too? Try taking a curve over a small field, base-changing to an extension, applying a random twist, and then asking for the cardinality. With my code it swould take no longer than on the original. Is that still true?

This still has to be checked.

comment:37 in reply to: ↑ 25 ; follow-up: Changed 3 years ago by jdemeyer

Replying to cremona:

I will ask the pari-devs about the other points.

John, did you do this? I don't find anything on the PARI mailing lists.

comment:38 in reply to: ↑ 37 Changed 3 years ago by cremona

Replying to jdemeyer:

Replying to cremona:

I will ask the pari-devs about the other points.

John, did you do this? I don't find anything on the PARI mailing lists.

I emailed Bill and Karim, CC-ing you, and this was their reply (last December):

On Fri, Dec 11, 2015 at 04:58:38PM +0000, John Cremona wrote:

Dear Karim and Bill,

  1. I put a lot of effort into the cases j=0 and j=1728, which in

characteristics 2 and 3 (when they are the same case!) required considerable care. For example, for p=2 the number of isomorphism classes is either 3 or 7 depending on the parity of the degree over F_2, i.e. that is the number of twists, so the idea is to determine which of the 3 or 7 cases you are in and apply the appropriate formula. What does pari do in these cases?

For p=3, this is the function F3xq_ellcardj(). The curve and its twists become identical in some degree-6 extension of the base field so we can identify the twist by using Kummer theory. The formula is not straightforward, but optimal for efficiency.

For p=2, I never finished to compute the equivalent formula (I think one need a degree 24 extension). So instead we use random points to discriminate between the possible candidates given by Deuring. This is done in F2xq_ellcard().

I wrote about one-sixth of the formula. If you know about the complete formula in this case, please tell me!

  1. If the j-invariant is defined over a much smaller field than the

field of definition of the curve, then what I do (or Sage does) is to point-count on some curve with that j, over the field generated over the prime field by j; use the standard formula to get the point-count of that curve over the original field of definition; and then decide on whether a final quadratic twist is needed. Does your code do that?

We do not always do it, because computing minimal polynomial was quite slow. Quite recently we have added faster methods to compute the minimal polynomial so we can revisit this point.

Practical example with this would be welcome.

Cheers, Bill.

comment:39 Changed 3 years ago by jpflori

I also sort of feel it might be useful to keep the old Sage point counting code (exhaustive/bsgs/special j's), modify the _pari version and keep the wrapper dealing with field of definition and special j's.

With this sort of code it is always better to be able to double check results btw two independent implementations.

comment:40 Changed 3 years ago by cremona

Thanks for saying that, as it sounds better not coming from me. I put a lot of work into that, knowing quite well that it was no good for cryptographically large cases.

comment:41 Changed 2 years ago by defeo

  • Cc defeo added

comment:42 Changed 2 years ago by roed

  • Keywords sd87 added

comment:44 Changed 2 years ago by jpflori

I would still suggest we keep John's code even though it's not used by default. It could still be used to double check PARI/GP results in doctests.

comment:45 Changed 2 years ago by jpflori

Same about Sage's naive and BSGS code.

comment:46 Changed 2 years ago by jpflori

And PARI/GP does not use the "minpoly/field of definition" trick as far as I know.

comment:47 Changed 20 months ago by cremona

Can this ticket be finished off?

comment:48 follow-up: Changed 20 months ago by jdemeyer

  • Dependencies #16949 deleted
  • Milestone changed from sage-7.4 to sage-8.3
  • Report Upstream changed from Fixed upstream, but not in a stable release. to Fixed upstream, in a later stable release.

The only remaining questions are:

  1. What to do with the old code (mostly written by John Cremona I think).
  1. Do we need to implement the "smaller field of definition of the j-invariant" trick? As far as I can tell, this is the only optimization which is in the Sage code but not in PARI/GP.

comment:49 in reply to: ↑ 48 Changed 19 months ago by roed

Replying to jdemeyer:

The only remaining questions are:

  1. What to do with the old code (mostly written by John Cremona I think).
  1. Do we need to implement the "smaller field of definition of the j-invariant" trick? As far as I can tell, this is the only optimization which is in the Sage code but not in PARI/GP.

I agree with jpflori that keeping the old code as something to compare with if bugs arise is a good idea. This also means that we can check to see if the j-invariant is in a subfield of the base field when selecting the algorithm.

comment:50 Changed 19 months ago by jdemeyer

I'm inclined to move all the old code to a new file, say src/sage/schemes/elliptic_curves/ell_finite_field_cardinality.py because then it becomes easier to differentiate between the old and the new code.

comment:51 Changed 19 months ago by git

  • Commit changed from 78133cf80ce8d5265139ad704f43a66e2f144a36 to e6b96caecce9269135e90bd8e366e1befdbb8a87

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

e6b96caElliptic curve point counting over F_q using PARI

comment:52 Changed 19 months ago by git

  • Commit changed from e6b96caecce9269135e90bd8e366e1befdbb8a87 to f61b91e02401f400482f17822d2ba4c98a4fe457

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

f61b91eElliptic curve point counting over F_q using PARI

comment:53 Changed 19 months ago by git

  • Commit changed from f61b91e02401f400482f17822d2ba4c98a4fe457 to c6d4402fa7ea6a0d2e8e3366c35e7d07ed6da394

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

c6d4402Elliptic curve point counting over F_q using PARI

comment:54 Changed 19 months ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:55 Changed 16 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:56 Changed 16 months ago by jdemeyer

If anybody cares about this ticket, let me know. Then I'll rebase this.

comment:57 Changed 16 months ago by cremona

I care -- and will review.

comment:58 Changed 16 months ago by jdemeyer

  • Dependencies set to #25567
  • Status changed from needs_review to needs_work

Even if not strictly required, it might be safest to base this on PARI 2.11 (#25567).

comment:59 Changed 12 months ago by git

  • Commit changed from c6d4402fa7ea6a0d2e8e3366c35e7d07ed6da394 to 209e7d619854f31458df537125422378a5cb9a01

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

209e7d6Elliptic curve point counting over F_q using PARI

comment:60 Changed 12 months ago by jdemeyer

  • Dependencies #25567 deleted
  • Report Upstream changed from Fixed upstream, in a later stable release. to N/A
  • Status changed from needs_work to needs_review

comment:61 Changed 12 months ago by roed

  • Reviewers set to David Roe, John Cremona
  • Status changed from needs_review to positive_review

Looks good to me!

comment:62 Changed 12 months ago by vbraun

  • Branch changed from u/jdemeyer/ticket/16931 to 209e7d619854f31458df537125422378a5cb9a01
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.