Faster GF(p^n) arithmetic for p^n >= 2^16

[malb]

The Pari+Python interface is too slow. ntl.ZZ_pE+Cython should be much faster.

CC: @sagetrac-ylchapuy @koffie

Component: basic arithmetic

Issue created by migration from https://trac.sagemath.org/ticket/417

[sagetrac-mabshoff]

comment:2

Hmm, could this have been fixed by the NTL wrapper rewrite?

Cheers,

Michael

[malb]

comment:4

No, this was not fixed by the NTL wrapper rewrite. NTL still needs to be actually used internally by FiniteField. This ticket requires two new implementations. GF(pⁿ) for p < (sizeof(long)<<3) and for p >= (sizeof(long)<<3). These are different classes in NTL and should both be wrapped.

[sagetrac-johanbosman]

Replying to @malb:

The Pari+Python interface is too slow. ntl.ZZ_pE+Cython should be much faster.

I completely agree. How much work has been done on this yet and how much work still needs to be done?

[malb]

comment:7

I don't think anybody worked on this much. GF(2^e) was switched to NTL, but nothing else happened.

However, the GF(2^e) should be a reasonable starting point for doing other fields (word-sized primes and general primes).

Also, we should eventually move sparse moduli interally but that's for another project :)