faster GF(2^n) arithmetic for n >= 16

[malb]

Using a Python wrapper around Pari is too slow. ntl.GF2E on the other hand should be a lot faster.

Component: basic arithmetic

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

[malb]

Attachment: gf2e.patch.gz

[malb]

comment:3

The attached patch implements GF(2ⁿ) for n >= 16 using NTL's GF2E and also refactors FiniteField* such that writing GF(pⁿ) for pⁿ >= 2¹⁶ should be easier. This patch also fixes an issue with ntl.GF2X and applies cleanly against 2.8.9. 'make test' passes.

Speed:

sage: F1 = FiniteField_givaro(2^15,'a')
sage: F2 = FiniteField_ntl_gf2e(2^15,'a')
sage: F3 = FiniteField_ext_pari(2^15,'a')

sage: F1.polynomial()
a^15 + a^5 + a^4 + a^2 + 1
sage: F2.polynomial()
a^15 + a^5 + a^4 + a^2 + 1
sage: F3.polynomial()
a^15 + a^5 + a^4 + a^2 + 1

sage: e1 = F1.random_element(); f1 = F1.random_element()
sage: e2 = F2.random_element(); f2 = F2.random_element()
sage: e3 = F3.random_element(); f3 = F3.random_element()

sage: %timeit e1*f1
1000000 loops, best of 3: 249 ns per loop
sage: %timeit e2*f2
1000000 loops, best of 3: 496 ns per loop
sage: %timeit e3*f3
10000 loops, best of 3: 36.9 µs per loop

sage: %timeit e1+f1
1000000 loops, best of 3: 255 ns per loop
sage: %timeit e2+f2
1000000 loops, best of 3: 391 ns per loop
sage: %timeit e3+f3
10000 loops, best of 3: 12.9 µs per loop