Opened 11 years ago
Closed 6 years ago
#11548 closed enhancement (wontfix)
Basic implementation of Harley's point counting for elliptic curve.
Reported by: | jpflori | Owned by: | cremona |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | elliptic curves | Keywords: | point counting, satoh, elliptic curve, canonical lift, robert harley |
Cc: | jpflori, defeo | Merged in: | |
Authors: | Jean-Pierre Flori | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This is a basic implementation of Harley's point counting algorithm in characteristic 2 as presented in Vercauteren thesis (so with what is called there Norm Computation I).
It uses Sage's interface to Pari library for computations in Z_q.
It is absolutely not optimized.
A simple optimization would be to cythonize it and use direct calls to Pari or NTL/GF2X libraries.
It is faster than the basic FGH algo implementation of ticket #11448 :
sage: from sage.schemes.elliptic_curves.fgh_algo import compute_trace_char2 sage: from sage.schemes.elliptic_curves.harley_algo import harley_2 sage: K = GF(1<<160,'t') sage: a = K.random_element(); time print harley_2(a); time print compute_trace_char2(a); -735100818784167142776219 Time: CPU 7.37 s, Wall: 7.38 s -735100818784167142776219 Time: CPU 37.33 s, Wall: 37.36 s
Attachments (1)
Change History (12)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Cc defeo added
comment:2 Changed 10 years ago by
As I've just discovered a lot of wonderfull point counting methods have been implemented in PARI using the new finite fields structures. This includes SEA over non prime fields and Harley's algo over binary fields and (although I've not tested them yet) will without doubt make this ticket and #11448 completely disgusting and useless.
comment:3 Changed 10 years ago by
Or not yet... After making F2xq_elltrace_Harley exported, I got
? install("F2xq_elltrace_Harley","GG","F2t","libpari.so") ? T = ffinit(2,50) time = 4 ms. %4 = Mod(1, 2)*x^50 + Mod(1, 2)*x^49 + Mod(1, 2)*x^48 + Mod(1, 2)*x^46 + Mod(1, 2)*x^45 + Mod(1, 2)*x^44 + Mod(1, 2)*x^43 + Mod(1, 2)*x^42 + Mod(1, 2)*x^41 + Mod(1, 2)*x^40 + Mod(1, 2)*x^39 + Mod(1, 2)*x^35 + Mod(1, 2)*x^34 + Mod(1, 2)*x^33 + Mod(1, 2)*x^26 + Mod(1, 2)*x^25 + Mod(1, 2)*x^22 + Mod(1, 2)*x^21 + Mod(1, 2)*x^19 + Mod(1, 2)*x^15 + Mod(1, 2)*x^11 + Mod(1, 2)*x^10 + Mod(1, 2)*x^5 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x^2 + Mod(1, 2) ? y = ffgen(T, 'y) time = 0 ms. %5 = y ? F2t(y,T) time = 39,851 ms. %6 = 98923248483100497287855138223198441376622276816543759170939344050632861903564575734332225322251885038368470915416413353352613860702438103323074121900241551957651892513077763294421993705142333456548398460171219944927400293743992287189504350867209860811073990260449906304617608020895477312400466435470196047936215444128727730739236164366221246300432249865320526043269725720878655567530016812013892875754883213427106752419692304240919666830240369646854535046860150297393360479520487019121
That's strange, I may have broken something in the way.
comment:4 Changed 10 years ago by
The above timing is indeed wrong. Bill reports
? a=ffgen(ffinit(2,1024),'a);ellffinit([1,0,0,0,a],a,1); ? ## *** last result computed in 11,482 ms.
And I get similar results on my computer.
And indeed the trace looks a little too large for smtg over F250, so I badly used the library function from gp, not sure how to do this properly though.
comment:5 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:6 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:7 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:8 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:9 Changed 6 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
Superseded by #16931 and new PARI/GP functionalities.
comment:10 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:11 Changed 6 years ago by
- Resolution set to wontfix
- Status changed from positive_review to closed
Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).
Basic implementation of Harley's point counting algo.