|
The categories for elements in univariate polynomial rings
and their quotients are
are RngUPolElt and RngUPolResElt
Parent(p) : RngUPolElt -> RngUPol
Category(p) : RngUPolElt -> Cat
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
a eq b : RngUPolElt, RngUPolElt -> BoolElt
a ne b : RngUPolElt, RngUPolElt -> BoolElt
a in R : RngUPolElt, Rng -> BoolElt
a notin R : RngUPolElt, Rng -> BoolElt
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
ElementToSequence(p) : RngUPolElt -> [ RngElt ]
Eltseq(p) : RngUPolElt -> [ RngElt ]
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.
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
(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.
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
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.
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 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).
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|