Univariate Skew Polynomials

This module provides the SkewPolynomial. In the class hierarchy in Sage, the locution Skew Polynomial is used for a Ore polynomial without twisting derivation.

Warning

The current semantics of __call__() are experimental, so a warning is thrown when a skew polynomial is evaluated for the first time in a session. See the method documentation for details.

AUTHORS:

  • Xavier Caruso (2012-06-29): initial version

  • Arpit Merchant (2016-08-04): improved docstrings, fixed doctests and refactored classes and methods

  • Johan Rosenkilde (2016-08-03): changes for bug fixes, docstring and doctest errors

class sage.rings.polynomial.skew_polynomial_element.SkewPolynomial_generic_dense

Bases: sage.rings.polynomial.ore_polynomial_element.OrePolynomial_generic_dense

Generic implementation of dense skew polynomial supporting any valid base ring and twisting morphism.

conjugate(n)

Return self conjugated by \(x^n\), where \(x\) is the variable of self.

The conjugate is obtained from self by applying the \(n\)-th iterate of the twisting morphism to each of its coefficients.

INPUT:

  • \(n\) – an integer, the power of conjugation

EXAMPLES:

sage: R.<t> = QQ[]
sage: K = R.fraction_field()
sage: sigma = K.hom([1 + 1/t])
sage: S.<x> = K['x',sigma]
sage: a = t*x^3 + (t^2 + 1)*x^2 + 2*t
sage: b = a.conjugate(2); b
((2*t + 1)/(t + 1))*x^3 + ((5*t^2 + 6*t + 2)/(t^2 + 2*t + 1))*x^2 + (4*t + 2)/(t + 1)
sage: x^2*a == b*x^2
True

In principle, negative values for \(n\) are allowed, but Sage needs to be able to invert the twisting morphism:

sage: b = a.conjugate(-1)
Traceback (most recent call last):
...
NotImplementedError: inverse not implemented for morphisms of Fraction Field of Univariate Polynomial Ring in t over Rational Field

Here is a working example:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: T.<y> = k['y',Frob]
sage: u = T.random_element(); u
(2*t^2 + 3)*y^2 + (4*t^2 + t + 4)*y + 2*t^2 + 2
sage: v = u.conjugate(-1); v
(3*t^2 + t)*y^2 + (4*t^2 + 2*t + 4)*y + 3*t^2 + t + 4
sage: u*y == y*v
True
left_power_mod(exp, modulus)

Return the remainder of self**exp in the left euclidean division by modulus.

INPUT:

  • exp – an Integer

  • modulus – a skew polynomial in the same ring as self

OUTPUT:

Remainder of self**exp in the left euclidean division by modulus.

REMARK:

The quotient of the underlying skew polynomial ring by the principal ideal generated by modulus is in general not a ring.

As a consequence, Sage first computes exactly self**exp and then reduce it modulo modulus.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x + t
sage: modulus = x^3 + t*x^2 + (t+3)*x - 2
sage: a.left_power_mod(100,modulus)
(4*t^2 + t + 1)*x^2 + (t^2 + 4*t + 1)*x + 3*t^2 + 3*t
multi_point_evaluation(eval_pts)

Evaluate self at list of evaluation points.

INPUT:

  • eval_pts – list of points at which self is to be evaluated

OUTPUT:

List of values of self at the eval_pts.

Todo

This method currently trivially calls the evaluation function repeatedly. If fast skew polynomial multiplication is available, an asymptotically faster method is possible using standard divide and conquer techniques and minimal_vanishing_polynomial().

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x + t
sage: eval_pts = [1, t, t^2]
sage: c = a.multi_point_evaluation(eval_pts); c
[t + 1, 3*t^2 + 4*t + 4, 4*t]
sage: c == [ a(e) for e in eval_pts ]
True
operator_eval(eval_pt)

Evaluate self at eval_pt by the operator evaluation method.

INPUT:

  • eval_pt – element of the base ring of self

OUTPUT:

The value of the polynomial at the point specified by the argument.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: T.<x> = k['x',Frob]
sage: a = 3*t^2*x^2 + (t + 1)*x + 2
sage: a(t) #indirect test
2*t^2 + 2*t + 3
sage: a.operator_eval(t)
2*t^2 + 2*t + 3

Evaluation points outside the base ring is usually not possible due to the twisting morphism:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = t*x + 1
sage: a.operator_eval(1/t)
Traceback (most recent call last):
...
TypeError: 1/t fails to convert into the map's domain
 Univariate Polynomial Ring in t over Rational Field,
 but a `pushforward` method is not properly implemented
right_power_mod(exp, modulus)

Return the remainder of self**exp in the right euclidean division by modulus.

INPUT:

  • exp – an integer

  • modulus – a skew polynomial in the same ring as self

OUTPUT:

Remainder of self**exp in the right euclidean division by modulus.

REMARK:

The quotient of the underlying skew polynomial ring by the principal ideal generated by modulus is in general not a ring.

As a consequence, Sage first computes exactly self**exp and then reduce it modulo modulus.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x + t
sage: b = a^5  # indirect doctest
sage: b
x^5 + (2*t^2 + 4)*x^4 + (t^2 + 2)*x^3 + 2*x^2 + (4*t^2 + 2)*x + 2*t^2 + 4*t + 4
sage: b == a * a * a * a * a
True

sage: modulus = x^3 + t*x^2 + (t+3)*x - 2
sage: br = a.right_power_mod(5, modulus); br
(t + 1)*x^2 + (2*t^2 + t + 1)*x + 2*t^2 + 4*t + 2
sage: br == b % modulus
True

sage: a.right_power_mod(100, modulus)
(2*t^2 + 3)*x^2 + (t^2 + 4*t + 2)*x + t^2 + 2*t + 1

Negative exponents are supported:

sage: a^(-5) (x^5 + (2*t^2 + 4)*x^4 + (t^2 + 2)*x^3 + 2*x^2 + (4*t^2 + 2)*x + 2*t^2 + 4*t + 4)^(-1) sage: b * a^(-5) 1

However, they cannot be combined with modulus:

sage: a.right_power_mod(-10, modulus)
Traceback (most recent call last):
...
ValueError: modulus cannot be combined with negative exponent