Opened 10 months ago

Last modified 10 months ago

#21259 new enhancement

Karatsuba based methods in Skew Polynomials

Reported by: arpitdm Owned by:
Priority: major Milestone: sage-7.4
Component: algebra Keywords:
Cc: dlucas, jsrn, caruso, tscrim Merged in:
Authors: Xavier Caruso Reviewers:
Report Upstream: N/A Work issues:
Branch: u/arpitdm/karatsuba_methods_skew_polynomials (Commits) Commit: 5547542371caac40b3a1570c0bca8f4ab5c58ba1
Dependencies: #13215, #21088 Stopgaps:


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.

Change History (2)

comment:1 Changed 10 months ago by arpitdm

  • Branch set to u/arpitdm/karatsuba_methods_skew_polynomials

comment:2 Changed 10 months ago by jsrn

  • Authors set to Xavier Caruso
  • Cc caruso tscrim added
  • Commit set to 5547542371caac40b3a1570c0bca8f4ab5c58ba1

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:

1a06b09added methods for multi-point evaluation, minimum subspace polynomial and interpolation
9a2fad2merged changes from Tickets 13215 and 21088
eaca253integrated skew polynomial finite field into sage. removed some compile and doctest errors.
7664060removed 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.
a6e93e1added SEEALSO and TODO blocks and made small polishes to the documentation.
130b173improved documentation for skew_polynomials_finite_field.pyx file
15861b9documentation builds successfully.
2d67e0emerging updates
a2c4f06removed unused imports, signal statements. small fixes to documentation.
5547542added karatsuba based methods as is, from the original #13215 ticket
Note: See TracTickets for help on using tickets.