Opened 5 years ago
Last modified 5 years 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, GitHub, GitLab) | Commit: | 5547542371caac40b3a1570c0bca8f4ab5c58ba1 |
Dependencies: | #13215, #21088 | Stopgaps: |
Description
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 5 years ago by
- Branch set to u/arpitdm/karatsuba_methods_skew_polynomials
comment:2 Changed 5 years ago by
- Cc caruso tscrim added
- Commit set to 5547542371caac40b3a1570c0bca8f4ab5c58ba1
Note: See
TracTickets for help on using
tickets.
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:
added methods for multi-point evaluation, minimum subspace polynomial and interpolation
merged changes from Tickets 13215 and 21088
integrated skew polynomial finite field into sage. removed some compile and doctest errors.
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.
added SEEALSO and TODO blocks and made small polishes to the documentation.
improved documentation for skew_polynomials_finite_field.pyx file
documentation builds successfully.
merging updates
removed unused imports, signal statements. small fixes to documentation.
added karatsuba based methods as is, from the original #13215 ticket