Opened 8 years ago
Closed 4 years ago
#16931 closed enhancement (fixed)
Elliptic curve point counting over F_q using PARI
Reported by:  Jeroen Demeyer  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  elliptic curves  Keywords:  sd87 
Cc:  Peter Bruin, John Cremona, Kiran Kedlaya, JeanPierre Flori, Luca De Feo  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  David Roe, John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  209e7d6 (Commits, GitHub, GitLab)  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 8 years ago by
Cc:  Peter Bruin John Cremona added 

comment:2 Changed 8 years ago by
Description:  modified (diff) 

comment:3 Changed 8 years ago by
Description:  modified (diff) 

comment:4 Changed 8 years ago by
Description:  modified (diff) 

comment:5 Changed 8 years ago by
Dependencies:  #15767, #16927, #8373, #16930 → #15767, #16927, #8373, #16930, #16934 

comment:6 Changed 8 years ago by
Branch:  → u/jdemeyer/ticket/16931 

Created:  Sep 4, 2014, 12:54:32 PM → Sep 4, 2014, 12:54:32 PM 
Modified:  Sep 7, 2014, 9:31:47 PM → Sep 7, 2014, 9:31:47 PM 
comment:7 Changed 8 years ago by
Commit:  → 51a753d5ec93fcd9c0228450eb6623827d4c97b1 

Dependencies:  #15767, #16927, #8373, #16930, #16934 → #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 8 years ago by
Dependencies:  #15767, #16927, #8373, #16930, #16934, #16944 → #15767, #16927, #8373, #16930, #16934, #16944, #16946 

comment:9 Changed 8 years ago by
Commit:  51a753d5ec93fcd9c0228450eb6623827d4c97b1 → 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 8 years ago by
Commit:  f05d8c11fa2c57015063ab8466d07fb09d54493e → 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 8 years ago by
Dependencies:  #15767, #16927, #8373, #16930, #16934, #16944, #16946 → #15767, #16927, #8373, #16930, #16934, #16944, #16946, #16947 

comment:12 Changed 8 years ago by
Commit:  6a80f7f165f699d382a03b000d84ff4f35ef4d47 → 4f9c038c5050535412649afb1fb19f473a280700 

comment:13 Changed 8 years ago by
Commit:  4f9c038c5050535412649afb1fb19f473a280700 → 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 8 years ago by
Description:  modified (diff) 

comment:15 Changed 8 years ago by
Description:  modified (diff) 

comment:16 Changed 8 years ago by
Description:  modified (diff) 

comment:17 Changed 8 years ago by
Description:  modified (diff) 

Report Upstream:  N/A → Reported upstream. Developers acknowledge bug. 
comment:18 Changed 8 years ago by
Description:  modified (diff) 

Report Upstream:  Reported upstream. Developers acknowledge bug. → Fixed upstream, but not in a stable release. 
comment:19 Changed 7 years ago by
Dependencies:  #15767, #16927, #8373, #16930, #16934, #16944, #16946, #16947 → #16949 

Description:  modified (diff) 
Milestone:  sage6.4 → sage6.11 
Summary:  Elliptic curve point counting over F_q using new PARI → Elliptic curve point counting over F_q using PARI 
comment:20 Changed 7 years ago by
Commit:  2049945d20f8e5561da7b1e80ece0255d43b3bdd → d760c63324cf7f0b4f6656455ad5a044f43a5200 

comment:21 Changed 7 years ago by
Commit:  d760c63324cf7f0b4f6656455ad5a044f43a5200 → 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 7 years ago by
Status:  new → needs_review 

comment:23 followup: 36 Changed 7 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 7 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 followups: 26 27 37 Changed 7 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 Changed 7 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 Changed 7 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 7 years ago by
Cc:  Kiran Kedlaya added 

comment:29 Changed 6 years ago by
Cc:  JeanPierre Flori added 

comment:30 Changed 6 years ago by
Branch:  u/jdemeyer/ticket/16931 → u/kedlaya/ticket/16931 

Commit:  7e93e62ea717e4391ec2ae441ec161ff88f3fd2c → 2be66ca92ed226775dc5a2b92cb43657e20954c6 
comment:31 Changed 6 years ago by
I'm not sure I did this merge correctly. If not, we can switch back to jdemeyer's branch.
comment:33 Changed 6 years ago by
Milestone:  sage7.0 → sage7.4 

Status:  needs_review → needs_work 
And in any case, adding 4499 lines to src/sage/libs/pari/gen.pyx
cannot be right...
comment:34 Changed 6 years ago by
Branch:  u/kedlaya/ticket/16931 → u/jdemeyer/ticket/16931 

comment:35 Changed 6 years ago by
Commit:  2be66ca92ed226775dc5a2b92cb43657e20954c6 → 78133cf80ce8d5265139ad704f43a66e2f144a36 

comment:36 Changed 6 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 followup: 38 Changed 6 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 Changed 6 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 6 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 6 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 5 years ago by
Cc:  Luca De Feo added 

comment:42 Changed 5 years ago by
Keywords:  sd87 added 

comment:43 Changed 5 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 5 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:46 Changed 5 years ago by
And PARI/GP does not use the "minpoly/field of definition" trick as far as I know.
comment:48 followup: 49 Changed 4 years ago by
Dependencies:  #16949 

Milestone:  sage7.4 → sage8.3 
Report Upstream:  Fixed upstream, but not in a stable release. → 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 Changed 4 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 4 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 4 years ago by
Commit:  78133cf80ce8d5265139ad704f43a66e2f144a36 → 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 4 years ago by
Commit:  e6b96caecce9269135e90bd8e366e1befdbb8a87 → 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 4 years ago by
Commit:  f61b91e02401f400482f17822d2ba4c98a4fe457 → 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 4 years ago by
Status:  needs_work → needs_review 

comment:56 Changed 4 years ago by
If anybody cares about this ticket, let me know. Then I'll rebase this.
comment:58 Changed 4 years ago by
Dependencies:  → #25567 

Status:  needs_review → needs_work 
Even if not strictly required, it might be safest to base this on PARI 2.11 (#25567).
comment:59 Changed 4 years ago by
Commit:  c6d4402fa7ea6a0d2e8e3366c35e7d07ed6da394 → 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 4 years ago by
Dependencies:  #25567 

Report Upstream:  Fixed upstream, in a later stable release. → N/A 
Status:  needs_work → needs_review 
comment:61 Changed 4 years ago by
Reviewers:  → David Roe, John Cremona 

Status:  needs_review → positive_review 
Looks good to me!
comment:62 Changed 4 years ago by
Branch:  u/jdemeyer/ticket/16931 → 209e7d619854f31458df537125422378a5cb9a01 

Resolution:  → fixed 
Status:  positive_review → closed 
Never mind the timings, PARI does its own caching now...