Opened 6 years ago
Closed 2 years ago
#16931 closed enhancement (fixed)
Elliptic curve point counting over F_q using PARI
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.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 )
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 6 years ago by
 Cc pbruin cremona added
comment:2 Changed 6 years ago by
 Description modified (diff)
comment:3 Changed 6 years ago by
 Description modified (diff)
comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 Changed 6 years ago by
 Dependencies changed from #15767, #16927, #8373, #16930 to #15767, #16927, #8373, #16930, #16934
comment:6 Changed 6 years ago by
 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 6 years ago by
 Commit set to 51a753d5ec93fcd9c0228450eb6623827d4c97b1
 Dependencies changed from #15767, #16927, #8373, #16930, #16934 to #15767, #16927, #8373, #16930, #16934, #16944
New commits:
8286a4c  Add ffprimroot, fflog, fforder

63ec17a  Allow modulus="primitive" in finite field constructor

abcf8a6  Deprecate nonpolynomial modulus argument in constructor of implementations of finite fields

8cdbd79  Improve computation of jinvariant over smaller field

8f805a2  Trac 16934: always put finite field implementation in factory key

8923777  Trac 16934: remove method FiniteFieldFactory.other_keys()

5e2681e  Trac 16934: more cleaning up

ffb74fa  Trac 16934: add doctest

51a753d  Elliptic curve point counting over F_q using PARI

comment:8 Changed 6 years ago by
 Dependencies changed from #15767, #16927, #8373, #16930, #16934, #16944 to #15767, #16927, #8373, #16930, #16934, #16944, #16946
comment:9 Changed 6 years ago by
 Commit changed from 51a753d5ec93fcd9c0228450eb6623827d4c97b1 to f05d8c11fa2c57015063ab8466d07fb09d54493e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9ff6d12  Return FFELT in GF(q) > PARI conversion

9335f76  Add residue_field() method to polynomials over GF(p)

aeae7f9  Merge branches 'ticket/16944' and 'ticket/16946' into HEAD

f05d8c1  Elliptic curve point counting over F_q using PARI

comment:10 Changed 6 years ago by
 Commit changed from f05d8c11fa2c57015063ab8466d07fb09d54493e to 6a80f7f165f699d382a03b000d84ff4f35ef4d47
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6a80f7f  Elliptic curve point counting over F_q using PARI

comment:11 Changed 6 years ago by
 Dependencies changed from #15767, #16927, #8373, #16930, #16934, #16944, #16946 to #15767, #16927, #8373, #16930, #16934, #16944, #16946, #16947
comment:12 Changed 6 years ago by
 Commit changed from 6a80f7f165f699d382a03b000d84ff4f35ef4d47 to 4f9c038c5050535412649afb1fb19f473a280700
comment:13 Changed 6 years ago by
 Commit changed from 4f9c038c5050535412649afb1fb19f473a280700 to 2049945d20f8e5561da7b1e80ece0255d43b3bdd
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2049945  Elliptic curve point counting over F_q using PARI

comment:14 Changed 6 years ago by
 Description modified (diff)
comment:15 Changed 6 years ago by
 Description modified (diff)
comment:16 Changed 6 years ago by
 Description modified (diff)
comment:17 Changed 6 years ago by
 Description modified (diff)
 Report Upstream changed from N/A to Reported upstream. Developers acknowledge bug.
comment:18 Changed 6 years ago by
 Description modified (diff)
 Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, but not in a stable release.
comment:19 Changed 5 years ago by
 Dependencies changed from #15767, #16927, #8373, #16930, #16934, #16944, #16946, #16947 to #16949
 Description modified (diff)
 Milestone changed from sage6.4 to sage6.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 5 years ago by
 Commit changed from 2049945d20f8e5561da7b1e80ece0255d43b3bdd to d760c63324cf7f0b4f6656455ad5a044f43a5200
comment:21 Changed 5 years ago by
 Commit changed from d760c63324cf7f0b4f6656455ad5a044f43a5200 to 7e93e62ea717e4391ec2ae441ec161ff88f3fd2c
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7e93e62  Elliptic curve point counting over F_q using PARI

comment:22 Changed 5 years ago by
 Status changed from new to needs_review
comment:23 followup: ↓ 36 Changed 5 years ago by
Thanks for your work on this. First two few small points:
 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. p1, p+1 or p depending). I wondered about this, did some experiments, and then verified with the pari documentation.
 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 jinvariant. 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, basechanging 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 Sageonly implementation could be kept and used if some parameter 'algorithm' was set? The parameter could be 'pari' by default.
comment:24 followup: ↓ 25 Changed 5 years ago by
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 Sageonly 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 ; followups: ↓ 26 ↓ 27 ↓ 37 Changed 5 years ago by
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 Sageonly 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 paridevs about the other points.
comment:26 in reply to: ↑ 25 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
 Cc kedlaya added
comment:29 Changed 4 years ago by
 Cc jpflori added
comment:30 Changed 4 years ago by
 Branch changed from u/jdemeyer/ticket/16931 to u/kedlaya/ticket/16931
 Commit changed from 7e93e62ea717e4391ec2ae441ec161ff88f3fd2c to 2be66ca92ed226775dc5a2b92cb43657e20954c6
comment:31 Changed 4 years ago by
I'm not sure I did this merge correctly. If not, we can switch back to jdemeyer's branch.
comment:32 Changed 4 years ago by
I think it's better to look at #16949 first anyway.
comment:33 Changed 4 years ago by
 Milestone changed from sage7.0 to sage7.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 4 years ago by
 Branch changed from u/kedlaya/ticket/16931 to u/jdemeyer/ticket/16931
comment:35 Changed 4 years ago by
 Commit changed from 2be66ca92ed226775dc5a2b92cb43657e20954c6 to 78133cf80ce8d5265139ad704f43a66e2f144a36
comment:36 in reply to: ↑ 23 Changed 4 years ago by
Replying to cremona:
Secondly, the old code was careful to only ever do counting over the field generated over the prime field by the jinvariant. 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, basechanging 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 ; followup: ↓ 38 Changed 4 years ago by
Replying to cremona:
I will ask the paridevs 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 4 years ago by
Replying to jdemeyer:
Replying to cremona:
I will ask the paridevs about the other points.
John, did you do this? I don't find anything on the PARI mailing lists.
I emailed Bill and Karim, CCing 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,
 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 degree6 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 onesixth of the formula. If you know about the complete formula in this case, please tell me!
 If the jinvariant is defined over a much smaller field than the
field of definition of the curve, then what I do (or Sage does) is to pointcount on some curve with that j, over the field generated over the prime field by j; use the standard formula to get the pointcount 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 4 years ago by
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 4 years ago by
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 4 years ago by
 Cc defeo added
comment:42 Changed 3 years ago by
 Keywords sd87 added
comment:43 Changed 3 years ago by
From what I see in PARI/GP code, all special cases are now specially treated:
 p=2: http://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=blob;f=src/basemath/F2xqE.c;h=ea2ad6eb00c5d1f7c03046c454a2fb67aa61eb9e;hb=HEAD#l805 and commit http://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=blobdiff;f=src/basemath/F2xqE.c;h=3c183ebcd1bec9545fa489fb2f0303961b2d99b2;hp=a057f8c51201c23f7a7c54390c8f9e6c66c1387c;hb=b2648cdaec00f184010132847748c4dbfa90dfba;hpb=0135506024b4d42f388f68d7b74f41217dd93719
 p=3: http://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=blob;f=src/basemath/FlxqE.c;h=e91d28ccb66f4c24ffc165f84e667d2f76598741;hb=HEAD#l1576 and commit http://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=commit;h=3f93b26f2bdc7188bc59e11b033e2d067274ba14
 p>3: http://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=blob;f=src/basemath/FlxqE.c;h=e91d28ccb66f4c24ffc165f84e667d2f76598741;hb=HEAD#l1605 and http://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=blob;f=src/basemath/FpE.c;h=d1574d410a08b9ede9e68b8275afc00d1a18873e;hb=HEAD#l1946
comment:44 Changed 3 years ago by
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 3 years ago by
Same about Sage's naive and BSGS code.
comment:46 Changed 3 years ago by
And PARI/GP does not use the "minpoly/field of definition" trick as far as I know.
comment:47 Changed 3 years ago by
Can this ticket be finished off?
comment:48 followup: ↓ 49 Changed 3 years ago by
 Dependencies #16949 deleted
 Milestone changed from sage7.4 to sage8.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:
 What to do with the old code (mostly written by John Cremona I think).
 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 3 years ago by
Replying to jdemeyer:
The only remaining questions are:
 What to do with the old code (mostly written by John Cremona I think).
 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 jinvariant is in a subfield of the base field when selecting the algorithm.
comment:50 Changed 3 years ago by
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 3 years ago by
 Commit changed from 78133cf80ce8d5265139ad704f43a66e2f144a36 to e6b96caecce9269135e90bd8e366e1befdbb8a87
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e6b96ca  Elliptic curve point counting over F_q using PARI

comment:52 Changed 3 years ago by
 Commit changed from e6b96caecce9269135e90bd8e366e1befdbb8a87 to f61b91e02401f400482f17822d2ba4c98a4fe457
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f61b91e  Elliptic curve point counting over F_q using PARI

comment:53 Changed 3 years ago by
 Commit changed from f61b91e02401f400482f17822d2ba4c98a4fe457 to c6d4402fa7ea6a0d2e8e3366c35e7d07ed6da394
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c6d4402  Elliptic curve point counting over F_q using PARI

comment:54 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:55 Changed 2 years ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:56 Changed 2 years ago by
If anybody cares about this ticket, let me know. Then I'll rebase this.
comment:57 Changed 2 years ago by
I care  and will review.
comment:58 Changed 2 years ago by
 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 2 years ago by
 Commit changed from c6d4402fa7ea6a0d2e8e3366c35e7d07ed6da394 to 209e7d619854f31458df537125422378a5cb9a01
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
209e7d6  Elliptic curve point counting over F_q using PARI

comment:60 Changed 2 years ago by
 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 2 years ago by
 Reviewers set to David Roe, John Cremona
 Status changed from needs_review to positive_review
Looks good to me!
comment:62 Changed 2 years ago by
 Branch changed from u/jdemeyer/ticket/16931 to 209e7d619854f31458df537125422378a5cb9a01
 Resolution set to fixed
 Status changed from positive_review to closed
Never mind the timings, PARI does its own caching now...