Karatsuba based methods in Skew Polynomials

[5b3bd7e6-c3f3-4830-a555-991f5e6beec0]

We propose additional methods in the cdef class SkewPolynomial_finite_field_dense for improved multiplication and division of ring elements. We also propose a new class cdef class SkewPolynomial_finite_field_karatsuba to handle the basic skew polynomial operations in the finite field case.

Note: The original ticket #13215 first introduced this functionality. That was subsequently modified to support the basic implementation of skew polynomials and the karatsuba based methods from that ticket that were removed are being reintroduced here.

Depends on #13215 Depends on #21088

CC: @sagetrac-dlucas @johanrosenkilde @xcaruso @tscrim

Component: algebra

Author: Xavier Caruso

Branch/Commit: u/arpitdm/karatsuba_methods_skew_polynomials @ 5547542

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

[5b3bd7e6-c3f3-4830-a555-991f5e6beec0]

Branch: u/arpitdm/karatsuba_methods_skew_polynomials

[johanrosenkilde]

Author: Xavier Caruso

[johanrosenkilde]

comment:2

Note that the current code is more or less just what was in the original patch for #13215 related to Karatsuba multiplication/division. No effort has e.g. been made yet to accommodate for changes in #13215 since this addition was factored out.

---

Last 10 new commits:

1a06b09	added methods for multi-point evaluation, minimum subspace polynomial and interpolation
9a2fad2	merged changes from Tickets 13215 and 21088
eaca253	integrated skew polynomial finite field into sage. removed some compile and doctest errors.
7664060	removed leftpow and rightpow methods from SkewPolynomial_finite_field_dense class because they require the 'bound' method which in turn requires 'center'. this will be added in another separate ticket with the rest of the center stuff.
a6e93e1	added SEEALSO and TODO blocks and made small polishes to the documentation.
130b173	improved documentation for skew_polynomials_finite_field.pyx file
15861b9	documentation builds successfully.
2d67e0e	merging updates
a2c4f06	removed unused imports, signal statements. small fixes to documentation.
5547542	added karatsuba based methods as is, from the original #13215 ticket

[johanrosenkilde]

Commit: 5547542