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