The categories for elements in univariate polynomial rings and their quotients are are RngUPolElt and RngUPolResElt
The usual unary and binary ring operations are available for univariate polynomials, with the following notable restrictions.
Since inverses cannot generally be obtained in polynomial rings, division (using /) of polynomials is not allowed, and neither are negative powers. For polynomial rings over fields division by elements of the coefficient field are allowed.
The operators div and mod give results corresponding to the quotient and the remainder of division of the arguments. See the section on quotient and remainder for details.
The list belows contains the general ring element predicates. Note that not all functions are available for every coefficient ring.
The coefficients of the polynomial p∈R[x] in ascending order, as a sequence of elements of R.
Given a polynomial p∈R[x] and an integer i≥0, return the coefficient of the i-th power of x in f. (If i exceeds the degree of f then zero is returned.) The return value is an element of R.
Given elements p and m of a polynomial ring P=R[x], where m is a monomial (that is, has exactly one non-zero base coefficient, which must be 1), return the coefficient of m in p, as an element of the coefficient ring R.
Return the coefficient of the highest occurring power of x in p∈R[x], as an element of the coefficient ring R.
Return the coefficient of the lowest occurring power of x in p∈R[x], as an element of the coefficient ring R.
Return the constant term, ie. the coefficient of x0 as an element of the coefficient ring R.
Return the non-zero terms of the polynomial p∈P=R[x] in ascending order with respect to the degree, as a sequence of elements of P with ascending degrees.
Return the term of p∈P= R[x] with the highest occurring power of x, as an element of P. The coefficient of the result will be the leading coefficient of p.
Return the term of p∈P= R[x] with the lowest occurring power of x, as an element of P. The coefficient of the result will be the trailing coefficient of p.
The monomials of the univariate p, matching up with Coefficients(p), that is a sequence of powers of the indeterminate up to the degree of p.
Given a polynomial p∈R[x], return the positions in p for which there are non-zero coefficients, and the corresponding coefficients.
Given a polynomial p∈P= R[x] where R is a subring of the real field (the ring of integers Z, the rational field Q, or a real field), return the polynomial in Z[x] obtained from p by rounding all the coefficients of p.
The valuation of a polynomial p ∈R[x], that is, the exponent of the largest power of x which divides p. Note that the zero polynomial has valuation ∞.
The degree of a polynomial p ∈R[x], that is, the exponent of the largest power of x that occurs with non-zero coefficient. Note that the zero polynomial has degree -1.
Max: RngIntElt Default:
Given a polynomial p over one of a certain collection of coefficient rings, this function returns a sorted sequence of pairs of coefficient ring element and integer, where the ring element is a root of p in the coefficient ring, and the integer its multiplicity. Currently the coefficient rings that are allowed comprise complex and real fields, integers and rationals, finite fields and residue class rings with prime modulus. If the parameter Max is set to a non-negative number m, at most m roots are returned.
Given a polynomial p over one of a certain collection of coefficient rings as well as a ring S into which the coefficients of p can be coerced automatically, this function returns a sorted sequence of pairs of ring element and integer, where the ring element is a root of p in the ring S, and the integer its multiplicity. Currently the coefficient rings that are allowed comprise complex and real fields, integers and rationals, finite fields and residue class rings with prime modulus.
Given a polynomial p over the coefficient ring R this function returns true iff p has a root in R. If the result is true, the function also returns a root of p as a second return value. Currently the coefficient rings that are allowed comprise complex and real fields, integers and rationals, finite fields and residue class rings with prime modulus. Note that particularly for finite fields, this method may be much faster than the computation of all roots of the polynomial.
Given a polynomial p over the coefficient ring R and a ring S which contains R, this function returns true iff p has a root in S. If the result is true, the function also returns a root of p in S as a second return value. Currently the coefficient rings that are allowed comprise complex and real fields, integers and rationals, finite fields and residue class rings with prime modulus. Note that particularly for finite fields, this method may be much faster than the computation of all roots of the polynomial.
Bits: BoolElt Default: false
Beta: FldReElt Default: 1.0
Exponent: RngIntElt Default:
Finalshifts: RngIntElt Default:
Direct: BoolElt Default: false
Given a monic non-zero univariate integer polynomial p and two positive integers N and X, this function returns all x0's such that |x0| ≤X and P(x0)=0 [N], as long as X ≤0.5 .N1/d, where d is the degree of p.This function implements Coppersmith's algorithm to compute the small roots of a univariate polynomial modulo an integer [Cop96], as described in Alexander May's PhD thesis [May03]. It relies upon the LLL algorithm for reducing euclidean lattices [LLL82]. It is frequently used for cryptanalysing public-key cryptosystems (see the example below).
When Bits is set to {true}, the input X is read as 2X.
The parameter Beta can be set to any value in (0.0, 1.0]. The routine will then find all x0's such that |x0| ≤X and P(x0)=0 isomorphic to N', as long as X ≤0.5 .Nβ2/d, where d is the degree of p and N'≥Nβ is any divisor of N.
The Exponent and Finalshifts specify the shape of the lattice basis to be reduced. If Exponent is m, then pm will be the highest power of p used to build the lattice basis, and if Finalshifts is t, t shifts of pm will be used. Unless requested by the user, these parameters are chosen automatically.
Finally, the Direct option allows the user to require the lattice basis to be reduced at once, and not progressively while constructed. This is can be slower.
> SetSeed(1); > F<x> := PolynomialRing (Integers()); > length := 1024; > p:=NextPrime (2^(Round(length/2)): Proof:=false); > pi:=Pi(RealField()); > q:=NextPrime (Round (pi*p): Proof:=false); > N := p*q;Suppose that N is known, as well as an approximation of the factor q:
> hidden:=220; > approxq := q+Random(2^hidden-1);Our goal is to recover q from our knowledge of approxq. We are therefore interested in the small roots of the polynomial x - approxq modulo q, whose multiple N is known.
> A:=x-approxq; > time perturb:=SmallRoots (A, N, hidden : Bits, Beta:=0.5)[1]; Time 0.050 > q eq approxq-perturb; true
(Procedure.) Set the verbose printing level for the SmallRoots routine to be v. Currently the legal values for v are true, false, 0, 1 or 2 (false is the same as 0, and true is the same as 1).
Given a polynomial p∈P, return the derivative of p as an element of P.
Given a polynomial p∈P and an integer n ≥0, return the n-th derivative of p as an element of P.
Given a polynomial p∈P over a field of characteristic zero, return the formal integral of p as an element of P.
Given an element p of a polynomial ring P and an element r of a ring S, return the value of p evaluated at r. If r can be coerced into the coefficient ring R of P, the result will be an element of R. If r cannot be coerced to the coefficient ring, then an attempt is made to do a generic evaluation of p at r. In this case, the result will be an element of S.
This function finds a univariate polynomial that evaluates to the values V in the interpolation points I. Let K be a field and n>0 an integer; given sequences I and V, both consisting of n elements of K, return the unique univariate polynomial p over K of degree less than n such that p(I[i]) = V[i] for each 1≤i≤n.
The following function provides an inverse operation to composing polynomials.
All: BoolElt Default: true
Given a polynomial f defined over a field k, return all complete decompositions [f1, ..., fr] of f such that f(t) = fr( ... (f1(t)). These decompositions are found, as explained in [ACvHS17], by computing the subfield lattice of k(t)/k(f), which in turn, is found by first computing the principal subfields of this extension and then computing all intersections of principal subfields. These intersections are computed by joining partitions.
> k:=GF(3^2);
> P<x>:=PolynomialRing(k);
> f:=x^9-x;
> Decomposition(f);
[
[
x^3 + x,
x^3 + 2*x
],
[
x^3 + k.1^6*x,
x^3 + k.1^6*x
],
[
x^3 + k.1^2*x,
x^3 + k.1^2*x
],
[
x^3 + 2*x,
x^3 + x
]
]
> Decomposition(f : All := false);
[
[
x^3 + x,
x^3 + 2*x
]
]
> Evaluate($1[1][2], $1[1][1]) eq f;
true
Given elements f and g of the polynomial ring P=R[x], this function returns polynomials q (quotient) and r (remainder) in P such that f = q.g + r, and the degree of r is minimal. The leading coefficient of g has to be a non-zero divisor in R. If the leading coefficient of g is a unit, then the degree of r will be strictly less than that of g (taking the degree of 0 to be -1). Over the integers (R=Z) this will be true in general when the leading coefficient of g divides that of f.
The quotient q of f by g, where f and g are in the polynomial ring P=R[x]. Magma calculates the polynomials q (quotient) and r (remainder) in P such that f = q * g + r, and the degree of r is minimal. The leading coefficient of g has to be a unit. If the leading coefficient of g is a unit in R, then the degree of r will be strictly less than that of g (taking the degree of 0 to be -1). Over the integers (R=Z) this will be true in general when the leading coefficient of g divides that of f.To find r, use mod, and to find both q and r, use Quotrem.
Return whether the polynomial f is exactly divisible by the polynomial g; that is, whether there exists q with f=qg. If so, return also the exact divisor q.
Assuming that the polynomial f is exactly divisible by the polynomial g, return the exact quotient of f by g (as a polynomial in the same polynomial ring). An error results if g does not divide f exactly.
The remainder r upon division of f by g, where f and g are in the polynomial ring P=R[x]. Magma calculates the polynomials q (quotient) and r (remainder) in P such that f = q * g + r, and the degree of r is minimal. The leading coefficient of g has to be a non-zero divisor. If the leading coefficient of g is a unit in R, then the degree of r will be strictly less than that of g (taking the degree of 0 to be -1). Over the integers (R=Z) this will be true in general when the leading coefficient of g divides that of f.To find q, use div, and to find both q and r, use Quotrem.
The exponent of the highest power of the polynomial g which divides the polynomial f.
The reductum of a polynomial f, which is the polynomial obtained by removing the leading term of f.
Given polynomials f, g in P=R[x], where R is an integral domain, this function returns the pseudo-remainder r of f and g defined as follows. Let d be the maximum of 0 and deg(f) - deg(g) + 1, and let c be the leading coefficient of g; then r will be the unique polynomial in P such that cd.f=q.g + r and the degree of r is less than that of g (possibly -1 for r=0).
Return the Euclidean norm of the univariate polynomial p∈P, where the Euclidean norm is the function that makes P into a Euclidean ring, which is the degree function.
The following functions allow modular arithmetic for univariate polynomials over a field without the need to move into the quotient ring. See also the description of mod in the section on quotient and remainder.
Given univariate polynomials f and g in K[x] over a field K, return fn mod g as an element of K[x]. Here n must be a non-negative integer, and g is allowed to be a constant polynomial.
Given two sequences X and M of polynomials where the elements in M are assumed to be pairwise coprime, find a single polynomial t that solve the modular equation Xi = t modulo Mi.
The reciprocal of the given univariate polynomial.
The polynomial whose roots are the nth powers of the roots of the given polynomial (which should have coefficients in some field).
The transformation of the univariate polynomial f under the linear fractional transformation given by the 2 by 2 matrix M (obtained by homogenizing f and making a linear substitution).