Basic implementation of Harley's point counting for elliptic curve.

[jpflori]

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

[jpflori]

Basic implementation of Harley's point counting algo.

[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.

[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.

[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 F₂⁵⁰, so I badly used the library function from gp, not sure how to do this properly though.

[jpflori]

Superseded by #16931 and new PARI/GP functionalities.

[embray]

Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).