Opened 8 years ago

Closed 3 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)

trac_11548-harley-pari.patch (23.9 KB) - added by jpflori 8 years ago.
Basic implementation of Harley's point counting algo.

Download all attachments as: .zip

Change History (12)

Changed 8 years ago by jpflori

Basic implementation of Harley's point counting algo.

comment:1 Changed 8 years ago by defeo

  • Cc defeo added

comment:2 Changed 7 years ago by jpflori

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 7 years ago by jpflori

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 7 years ago by jpflori

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

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 3 years ago by jpflori

  • 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 3 years ago by jpflori

  • Status changed from needs_review to positive_review

comment:11 Changed 3 years ago by embray

  • 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).

Note: See TracTickets for help on using tickets.