Element Operations#

The categories for elements in univariate polynomial rings and their quotients are 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 [Coppersmith, 1996], as described in Alexander May’s PhD thesis [May, 2003]. It relies upon the LLL algorithm for reducing euclidean lattices [Lenstra et al., 1982]. 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: Small Roots Usage (ex-2984f7)#

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;

Run in calculator

Suppose that \(N\) is known, as well as an approximation of the factor \(q\):

> hidden:=220;
> approxq := q+Random(2^hidden-1);

Run in calculator

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

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 [Allem et al., 2017], 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: Decomp Ex (ex-b0e795)#

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

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