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:
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 ofself
.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: # needs sage.rings.finite_rings sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: T.<y> = k['y',Frob] sage: u = T.random_element() sage: v = u.conjugate(-1) sage: u*y == y*v True
- left_power_mod(exp, modulus)#
Return the remainder of
self**exp
in the left euclidean division bymodulus
.INPUT:
exp
– an Integermodulus
– a skew polynomial in the same ring asself
OUTPUT:
Remainder of
self**exp
in the left euclidean division bymodulus
.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 modulomodulus
.EXAMPLES:
sage: # needs sage.rings.finite_rings 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 whichself
is to be evaluated
OUTPUT:
List of values of
self
at theeval_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: # needs sage.rings.finite_rings 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
ateval_pt
by the operator evaluation method.INPUT:
eval_pt
– element of the base ring ofself
OUTPUT:
The value of the polynomial at the point specified by the argument.
EXAMPLES:
sage: # needs sage.rings.finite_rings 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 bymodulus
.INPUT:
exp
– an integermodulus
– a skew polynomial in the same ring asself
OUTPUT:
Remainder of
self**exp
in the right euclidean division bymodulus
.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 modulomodulus
.EXAMPLES:
sage: # needs sage.rings.finite_rings 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: # needs sage.rings.finite_rings 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) # needs sage.rings.finite_rings Traceback (most recent call last): ... ValueError: modulus cannot be combined with negative exponent