Base Class for Skew Polynomials over Finite Fields

[arpitdm]

General, dense, univariate Skew Polynomials and SkewPolynomial Rings over generic commutative base rings are already supported in Ticket #13215. This ticket proposes adding functionality for additional methods and optimized algorithms for such Skew Polynomials specifically over Finite Fields. This includes:

1. Class SkewPolynomial_finite_field(SkewPolynomial_generic_dense)
2. Class SkewPolynomialRing_finite_field(SkewPolynomialRing_general)

Note: There are a number of additional functionalities such as a class for Karatsuba multiplication in finite fields, center of skew polynomial ring, factorization and irreducibility that were written in the original #13215. Those will be added in separate tickets.

Depends on #13215

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

Component: algebra

Keywords: sd75

Author: Xavier Caruso, Arpit Merchant

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

[arpitdm]

Branch: u/arpitdm/finite_fields_skew_polynomial

[arpitdm]

comment:2

I've added the relevant classes and methods fixed all doctest errors that remained, added missing documentation and tests, and cleaned up the code. I am facing a couple of tiny issues with the minimum subspace polynomial (MSP), multi-point evaluation (MPE) and interpolation methods. I think I should have them ready in a short while.
Please let me know what else I can add to this ticket. If there isn't anything, then I'll open the ticket for review once I add MSP, MPE and interpolation.

---

Last 10 new commits:

e189fec	removed side.py
1f62ef4	added a section related to skew polynomils in the index file.
abbd05e	removed double imports and unused classes and methods
8b337c5	improved description of module, definition of skew polynomial, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of a couple of methods.
e0f3f42	changes to incorporate merging and into
0c8f6ec	removed unnecessary imports
0641ecf	improved description of module, definition of skew polynomial ring, removed unnecessary imports, improved informativeness of docstrings, input sanitization and documentation of some methods. cleaned up code.
22eab5d	same as previous commit
e46f778	added the finite field files without karatsuba, center, irreducibility and factor stuff. cleaned up code. fixed doctest errors.
f4b8413	added missing documentation and some tests. added class SkewPolynomialRing_finite_field.

[arpitdm]

Commit: f4b8413

[sagetrac-git]

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

d49392e	resolved single and double back tick formatting inconsistencies.
1a06b09	added methods for multi-point evaluation, minimum subspace polynomial and interpolation

[sagetrac-git]

Changed commit from f4b8413 to 1a06b09

[johanrosenkilde]

comment:4

I've been thinking about whether the functions minimum_subspace_polynomial, multi_point_evaluation and interpolation_polynomial make any sense for general skew polynomial rings. I politely doubt that you were really considering this when you put the functions in SkewPolynomial_general (since the current implementation not at all works for general skew polynomial rings). But it turns out they do make sense and the algorithms more-or-less immediately works. So I suggest those three functions should be in their own tickets.

• It seems minimum_subspace_polynomial does make sense in general, but it should be called something different and the implementation should be fixed. Firstly, the name and your current implementation is a verbose translation from linearized polynomials. This obviously leads to confusion and incorrect behaviour for even skew polynomials over finite fields with twist map the frobenius (for instance, in linearized polynomials x<sup>(q</sup>i) translates to x^i in skew polynomials).

  My suggestion is to call the function minimal_vanishing_polynomial. Given elements a1,...,an, it is defined as the (unique) minimal-degree polynomial p
  such that p is monic (leading coefficient is 1) and p(ai) = 0 for i=1,...,n.

• The implementation of course also needs to be slightly modified:

  - Given an empty list of points, return 1.
  
  - Given a singleton point a, return x - sigma(a)/a.   (use pen-and-paper to see that I am right)
  
  - Given a list of points, use divide and conquer as you do now.
  

• Then multi_point_evaluation also makes sense, and it's implementation is close to what you have now: as I've mentioned before, you should use sigma instead of q-powering everywhere. While were on it, you write "pow(a, pow(q, 0))" several places, but this is clearly just "a"!

• x = self([0,1]) should be x = self._parent.gen().

• Instead of lines such as

  ```
        y = []
        y.append(bla-bla) 
        return y
  ```
  
  you should write 
  
  ```
        return [ bla-bla ]
  ```
  

• In multi_point_evaluation you have a duplicate line r = .... with return .... Worse, that line is incorrect: you shouldn't convert to sets, then union, then convert back to a list (you lose ordering of evaluations, and the user wants to know that e.g. multiple input evaluates to, say, 1). Just concatenate the two lists: self.multi_point_evaluation(R_A, A) + self.multi_point_evaluation(R_B, B).

• minimum_subspace_polynomial and multi_point_evaluation are mutually recursive and will generate the same minimum subspace polynomials an exponential number of times right now. We need to add caching: add @cached_method to minimum_subspace_polynomial.

• multi_point_evaluation is a fairly complicated procedure compared to just calling n times __call__. Try to do timings to see if it is worth it. (Asymptotically, there is only a gain if some fast multiplication and quo_rem of skew polynomials is implemented, which it isn't).

• With minimum_subspace_polynomial and multi_point_evaluation then interpolation_polynomial also makes sense for general skew polynomials. The implementation you wrote immediately works, except that you again should replace pow(x, (pow(q,0) with self._parent.one(), and x = self([0,1]) with x = self._parent.gen().

• Note that all three functions are easily tested: for the minimum_subspace_polynomial, just check the degree of the output and that it evaluates to zero on all the input poins. For multi_point_evaluation, just check that the evaluations match using single __call__'s. For interpolation_polynomial just check that the degree is less than the number of points, and that the output evaluates correctly at all input. Be sure to test your functions on skew polynomials over finite fields, both with sigma being the Frobenius or a power of Frobenius, and also on skew polynomials over another ring.

[johanrosenkilde]

comment:5

The point of the specialised implementations over finite fields is to have improved performance. Do you have timing results to demonstrate that each arithmetic operation is now faster than with the generic implementation?

[sagetrac-dlucas]

comment:6

Hello,

I have some more comments:

• Is there any reason why cdef methods in skew_polynomial_finite_field.pyx are not doctested?
• In the same module, a lot of methods do not respect documentation conventions. See cdef SkewPolynomial_finite_field_dense _rgcd for instance, whose documentation is this single sentence: Fast right gcd.. Some methods (e.g. _rightpow_, _leftpow) do not even have this Return(s) blah blah line which explains what they're supposed to do...
• skew_polynomial_finite_field.pyx's title is This module implements skew polynomials over finite fields.. I think it should be changed to Skew polynomials over finite fields, or something equivalent.
• A lot of elements are not properly formatted in docstrings of skew_polynomial_finite_field.pyx: it should be <double backtick>self<double backtick> instead of self, etc.
• In class SkewPolynomialRing_finite_field, docstring of twist_map is not helpful as it says Return the twist map.

[tscrim]

comment:7

cdef methods/functions are not callable from Sage (i.e., python). They technically don't need to be doctested. However, there should be an EXAMPLES:: that has a function that (indirectly) calls the method/function in question.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

b52fc95	using cached versions of 0 and 1 wherever applicable.
6fb186a	changed Returns to Return and Note to NOTE for consistency. Removed trailing whitespaces. codeformatting for True, False and None objects.
1204f2d	the current implementation of the :meth: `__call__` was incorrect. added the correct and cythonized version.
7e076fa	moved module level docs to user entry point at the class level so that they are accessible at command line. added a SEEALSO block.
69fecc4	converted :meth: into a cpdef method with output type list. removed and directly use the attribute.
271bfac	removed some commented code and trailing whitespaces.
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.

[sagetrac-git]

Changed commit from 1a06b09 to a6e93e1