wrap NTL's lzz_pE and lzz_pEX and use them

[sagetrac-ylchapuy]

This should fasten polynomial arithmetic over finite fields of small characteristic.

Component: algebra

Keywords: ntl

Author: Yann Laigle-Chapuy

Reviewer: roed

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

[sagetrac-ylchapuy]

Attachment: trac_8109-lzz_pEX.patch.gz

needs #7841 (I guess)

[sagetrac-ylchapuy]

comment:1

Preliminary version.

note: this is mostly a copy of existing files for wrapping ZZ_pE and ZZ_pEX with
'sed s/ZZ/zz/g' applied.

warning: there is no test (yet) for checking that the modulus is < NTL_SP_BOUND

still, doctests pass and here are some results:

sage: c=ntl.zz_pEContext(ntl.zz_pX([1,1,1,1,1], 19800713)) 
sage: a = ntl.zz_pE([3,2], c); b = ntl.zz_pE([1,2], c)
sage: f = ntl.zz_pEX([a, b, b])
sage: p = f**123
sage: q = p+f**77+f
sage: 
sage: C=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1,1,1], 19800713)) 
sage: A = ntl.ZZ_pE([3,2], C); B = ntl.ZZ_pE([1,2], C)
sage: F = ntl.ZZ_pEX([A, B, B])
sage: P = F**123
sage: Q = P+F**77+F
sage: 
sage: %timeit p+q
625 loops, best of 3: 59.6 µs per loop
sage: %timeit P+Q
625 loops, best of 3: 180 µs per loop
sage: 
sage: %timeit p*q
125 loops, best of 3: 2.62 ms per loop
sage: %timeit P*Q
125 loops, best of 3: 5.65 ms per loop
sage: 
sage: %timeit p.gcd(q)
125 loops, best of 3: 7.28 ms per loop
sage: %timeit P.gcd(Q)
5 loops, best of 3: 62.5 ms per loop
sage: 
sage: %timeit p**17
5 loops, best of 3: 58 ms per loop
sage: %timeit P**17
5 loops, best of 3: 129 ms per loop

[sagetrac-ylchapuy]

Changed keywords from none to ntl

[sagetrac-ylchapuy]

comment:2

Replying to @sagetrac-ylchapuy:

warning: there is no test (yet) for checking that the modulus is < NTL_SP_BOUND

I must be tired... there is a check, it's done in the lzz_p class.

I guess this one is ready for review then. I will open another ticket to do the same as #7841 latter.

[sagetrac-ylchapuy]

use both patches

[sagetrac-ylchapuy]

comment:3

Attachment: trac_8109-lzz_pEX-part2.patch.gz

Finally, this is such a small patch that I add it here.
With both patches applied, the default implementation for polynomial ring is now based on NTL, and uses type ZZ or lzz depending on the characteristic (tested against NTL_SP_BOUND).

[roed314]

Reviewer: roed