Element Operations

The categories for elements in univariate polynomial rings and their quotients are RngUPolElt and RngUPolResElt

Parent and Category

Parent(p): RngUPolElt -> RngUPol

Category(p): RngUPolElt -> Cat

Arithmetic Operators

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.

+ a: RngUPolElt -> RngUPolElt

- a: RngUPolElt -> RngUPolElt

a + b: RngUPolElt, RngUPolElt -> RngUPolElt

a - b: RngUPolElt, RngUPolElt -> RngUPolElt

a * b: RngUPolElt, RngUPolElt -> RngUPolElt

a ^ k: RngUPolElt, RngIntElt -> RngUPolElt

a / b: RngUPolElt, RngElt -> FldFunUElt

a div b: RngUPolElt, RngUPolElt -> RngUPolElt

a mod b: RngUPolElt, RngUPolElt -> RngUPolElt

a +:= b: RngUPolElt, RngUPolElt -> RngUPolElt

a -:= b: RngUPolElt, RngUPolElt -> RngUPolElt

a *:= b: RngUPolElt, RngUPolElt -> RngUPolElt

Equality and Membership

a eq b: RngUPolElt, RngUPolElt -> BoolElt

a ne b: RngUPolElt, RngUPolElt -> BoolElt

a in R: RngUPolElt, Rng -> BoolElt

a notin R: RngUPolElt, Rng -> BoolElt

Predicates on Ring Elements

The list belows contains the general ring element predicates. Note that not all functions are available for every coefficient ring.

IsZero(a): RngUPolElt -> BoolElt

IsOne(a): RngUPolElt -> BoolElt

IsMinusOne(a): RngUPolElt -> BoolElt

IsNilpotent(a): RngUPolElt -> BoolElt

IsIdempotent(a): RngUPolElt -> BoolElt

IsUnit(a): RngUPolElt -> BoolElt

IsZeroDivisor(a): RngUPolElt -> BoolElt

IsRegular(a): RngUPolElt -> BoolElt

IsIrreducible(a): RngUPolElt -> BoolElt

IsPrime(a): RngUPolElt -> BoolElt

IsMonic(a): RngUPolElt -> BoolElt

Coefficients and Terms

Coefficients(p): RngUPolElt -> [ RngElt ]

ElementToSequence(p): RngUPolElt -> [ RngElt ]

Eltseq(p): RngUPolElt -> [ RngElt ]

The coefficients of the polynomial \(p\in R[x]\) in ascending order, as a sequence of elements of \(R\).

Coefficient(p, i): RngUPolElt, RngIntElt -> RngElt

Given a polynomial \(p\in R[x]\) and an integer \(i\geq 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\).

MonomialCoefficient(p, m): RngUPolElt, RngUPolElt -> RngElt

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\).

LeadingCoefficient(p): RngUPolElt -> RngElt

Return the coefficient of the highest occurring power of \(x\) in \(p\in R[x]\), as an element of the coefficient ring \(R\).

TrailingCoefficient(p): RngUPolElt -> RngElt

Return the coefficient of the lowest occurring power of \(x\) in \(p\in R[x]\), as an element of the coefficient ring \(R\).

ConstantCoefficient(p): RngUPolElt -> RngElt

Return the constant term, i.e., the coefficient of \(x^0\) as an element of the coefficient ring \(R\).

Terms(p): RngUPolElt -> [ RngUPolElt ]

Return the non-zero terms of the polynomial \(p\in P=R[x]\) in ascending order with respect to the degree, as a sequence of elements of \(P\) with ascending degrees.

LeadingTerm(p): RngUPolElt -> RngUPolElt

Return the term of \(p\in 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\).

TrailingTerm(p): RngUPolElt -> RngUPolElt

Return the term of \(p\in 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\).

Monomials(p): RngUPolElt -> SeqEnum

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\).

Support(p): RngUPolElt -> [RngIntElt], [RngElt]

Given a polynomial \(p\in R[x]\), return the positions in \(p\) for which there are non-zero coefficients, and the corresponding coefficients.

Round(p): RngUPolElt -> RngUPolElt

Given a polynomial \(p\in P= R[x]\) where \(R\) is a subring of the real field (the ring of integers \({\mathbb{Z}}\), the rational field \({\mathbb{Q}}\), or a real field), return the polynomial in \(Z[x]\) obtained from \(p\) by rounding all the coefficients of \(p\).

Valuation(p): RngUPolElt -> RngIntElt

The valuation of a polynomial \(p \in R[x]\), that is, the exponent of the largest power of \(x\) which divides \(p\). Note that the zero polynomial has valuation \(\infty\).

Degree

Degree(p): RngUPolElt -> RngIntElt

The degree of a polynomial \(p \in 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\).

Roots

Roots(p): RngUPolElt -> [ < RngElt, RngIntElt> ]

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.

Roots(p, S): RngUPolElt -> [ < RngElt, RngIntElt> ]

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.

HasRoot(p): RngUPolElt -> BoolElt, RngElt

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.

HasRoot(p, S): RngUPolElt, Rng -> BoolElt, RngElt

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.

SmallRoots(p, N, X): RngUPolElt, RngElt, RngElt -> [RngElt]

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 \(x_0\)’s such that \(|x_0| \leq X\) and \(P(x_0)=0 \ [N]\), as long as \(X \leq 0.5 \cdot N^{1/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 \(2^X\). The parameter Beta can be set to any value in \((0.0, 1.0]\). The routine will then find all \(x_0\)’s such that \(|x_0| \leq X\) and \(P(x_0)=0 \cong N'\), as long as \(X \leq 0.5 \cdot N^{\beta^2/d}\), where \(d\) is the degree of \(p\) and \(N'\geq N^{\beta}\) is any divisor of \(N\). The Exponent and Finalshifts specify the shape of the lattice basis to be reduced. If Exponent is \(m\), then \(p^m\) will be the highest power of \(p\) used to build the lattice basis, and if Finalshifts is \(t\), \(t\) shifts of \(p^m\) 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.

Example: Factoring an RSA Modulus with Small Roots (ex-2984f7)

Run in calculator (opens in a new tab)Copy input

We show how to use the SmallRoots routine to factor an RSA modulus when some most significant bits of one of the factors is known. We first generate an RSA modulus.

> 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

Run in calculator (opens in a new tab)Copy input

SetVerbose("SmallRoots", v): MonStgElt, RngIntElt

(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).

Derivative, Integral

Derivative(p): RngUPolElt -> RngUPolElt

Given a polynomial \(p\in P\), return the derivative of \(p\) as an element of \(P\).

Derivative(p, n): RngUPolElt, RngIntElt -> RngUPolElt

Given a polynomial \(p\in P\) and an integer \(n \geq 0\), return the \(n\)-th derivative of \(p\) as an element of \(P\).

Integral(p): RngUPolElt -> RngUPolElt

Given a polynomial \(p\in P\) over a field of characteristic zero, return the formal integral of \(p\) as an element of \(P\).

Evaluation, Interpolation

Evaluate(p, r): RngUPolElt, RngElt -> RngElt

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\).

Interpolation(I, V): [ RngElt ], [ RngElt ] -> RngUPolElt

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\leq i\leq n\).

Decomposition

The following function provides an inverse operation to composing polynomials.

Decomposition(f): RngUPolElt -> [[RngUPolElt]]

All: BoolElt                    Default: true

Given a polynomial \(f\) defined over a field \(k\), return all complete decompositions \([f_1,\ldots, f_r]\) of \(f\) such that \(f(t) = f_r(\ldots(f_1(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.

Example: Polynomial Decomposition (ex-b0e795)

Run in calculator (opens in a new tab)Copy input

We show a decomposition of a polynomial and the corresponding evaluations which retrieve the polynomial which was decomposed.

> 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

Run in calculator (opens in a new tab)Copy input

Quotient and Remainder

Quotrem(f, g): RngUPolElt, RngUPolElt -> RngUPolElt, RngUPolElt

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\cdot 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={\mathbb{Z}}\)) this will be true in general when the leading coefficient of \(g\) divides that of \(f\).

f div g: RngUPolElt, RngUPolElt -> RngUPolElt

The quotient of the polynomial \(f\) by \(g\), which is the first return value of Quotrem described above.

IsDivisibleBy(f, g): RngUPolElt, RngUPolElt -> BoolElt, RngUPolElt

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\).

ExactQuotient(f, g): RngUPolElt, RngUPolElt -> RngUPolElt

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.

f mod g: RngUPolElt, RngUPolElt -> RngUPolElt

The remainder of division of the polynomial \(f\) by \(g\), which is the second return value of Quotrem described above.

Valuation(f, g): RngUPolElt, RngUPolElt -> RngIntElt

The exponent of the highest power of the polynomial \(g\) which divides the polynomial \(f\).

Reductum(f): RngUPolElt -> RngUPolElt

The reductum of a polynomial \(f\), which is the polynomial obtained by removing the leading term of \(f\).

PseudoRemainder(f, g): RngUPolElt, RngUPolElt -> RngUPolElt

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 \(c^d\cdot f=q\cdot g + r\) and the degree of \(r\) is less than that of \(g\) (possibly \(-1\) for \(r=0\)).

EuclideanNorm(p): RngUPol -> RngIntElt

Return the Euclidean norm of the univariate polynomial \(p\in P\), where the Euclidean norm is the function that makes \(P\) into a Euclidean ring, which is the degree function.

Modular Arithmetic

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.

Modexp(f, n, g): RngUPolElt, RngIntElt, RngUPolElt -> RngUPolElt

Given univariate polynomials \(f\) and \(g\) in \(K[x]\) over a field \(K\), return \(f^n \bmod g\) as an element of \(K[x]\). Here \(n\) must be a non-negative integer, and \(g\) is allowed to be a constant polynomial.

ChineseRemainderTheorem(X, M): [RngUPolElt], [RngUPolElt] -> RngUPolElt

CRT(X, M): [RngUPolElt], [RngUPolElt] -> RngUPolElt

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 \(X_i = t\) modulo \(M_i\).

Other Operations

ReciprocalPolynomial(f): RngUPolElt -> RngUPolElt

The reciprocal of the given univariate polynomial.

PowerPolynomial(f, n): RngUPolElt, RngIntElt -> RngUPolElt

The polynomial whose roots are the \(n\)th powers of the roots of the given polynomial (which should have coefficients in some field).

f ^ M: RngUPolElt, Mtrx -> RngUPolElt

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).