use NTL's MinPolyMod()

[yyyyx4]

NTL implements Shoup's algorithm https://shoup.net/papers/mpol.pdf for minimal polynomials of algebraic elements over finite fields.

This patch adds call paths from PolynomialQuotientRingElement.minpoly() and RingExtensionWithBasisElement.minpoly() to NTL's MinPolyMod() function, yielding massive speedups in some important special cases.

Example code:

sage: K.<u> = GF((23,5))
....: L.<v> = K.extension(42)
....: LK = L.over(K)
....: _ = LK(L.random_element()).minpoly()  # warm up
....: %timeit LK(L.random_element()).minpoly()

Sage 9.7:

2.47 s ± 25.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

This branch:

49.6 ms ± 546 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Component: algebra

Author: Lorenz Panny

Branch/Commit: d230ff8

Reviewer: Frédéric Chapoton

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

[sagetrac-git]

Changed commit from 1a1e4a4 to 33171a8

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f29f31e	fix reference
33171a8	avoid detour through multivariate polynomial ring

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

23f2c2d	expose NTL's MinPolyMod() and use it
0e9a4e2	avoid detour through multivariate polynomial ring

[sagetrac-git]

Changed commit from 33171a8 to 0e9a4e2

[fchapoton]

comment:4

you could add the doi to the reference

https://doi.org/10.1145/309831.309859

so :doi:`10.1145/309831.309859`

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8eba4eb

add DOI to reference

[sagetrac-git]

Changed commit from 0e9a4e2 to 8eba4eb

[yyyyx4]

comment:6

Sure, why not. Done.

[fchapoton]

comment:7

one failing doctest, see patchbot, that seems to be related to the changes done here

[yyyyx4]

comment:8

Sorry, that's a new test I added (and promptly got wrong). Fixing shortly.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d230ff8

fix doctest

[sagetrac-git]

Changed commit from 8eba4eb to d230ff8

[fchapoton]

comment:10

ok, I will give a positive review, unless you want to ask some more qualified expert in the domain

[fchapoton]

Reviewer: Frédéric Chapoton

[yyyyx4]

comment:11

Thank you!

[vbraun]

Changed branch from public/use_NTL_MinPolyMod to d230ff8