Opened 11 years ago

Closed 6 years ago

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

Reported by: Owned by: jpflori cremona major sage-duplicate/invalid/wontfix elliptic curves point counting, satoh, elliptic curve, canonical lift, robert harley jpflori, defeo Jean-Pierre Flori N/A

### 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
```

### Changed 11 years ago by jpflori

Basic implementation of Harley's point counting algo.

### comment:2 Changed 10 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 10 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 10 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 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:6 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:7 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:8 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:9 Changed 6 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 6 years ago by jpflori

• Status changed from needs_review to positive_review

### comment:11 Changed 6 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.