Internals of the Polynomial Manipulation Module

All polynomial manipulations are relative to a ground domain. For example, when factoring a polynomial like \(x^{10} - 1\), one has to decide what ring the coefficients are supposed to belong to, or less trivially, what coefficients are allowed to appear in the factorization. This choice of coefficients is called a ground domain. Typical choices include the integers \(\mathbb{Z}\), the rational numbers \(\mathbb{Q}\) or various related rings and fields. But it is perfectly legitimate (although in this case uninteresting) to factorize over polynomial rings such as \(k[Y]\), where \(k\) is some fixed field.

Thus the polynomial manipulation algorithms (both complicated ones like factoring, and simpler ones like addition or multiplication) have to rely on other code to manipulate the coefficients. In the polynomial manipulation module, such code is encapsulated in so-called domains. A domain is basically a factory object: it takes various representations of data, and converts them into objects with unified interface. Every object created by a domain has to implement the arithmetic operations \(+\), \(-\) and \(\times\). Other operations are accessed through the domain, e.g. as in ZZ.quo(ZZ(4), ZZ(2)).

Manipulation of sparse, distributed polynomials

Dense representations quickly require infeasible amounts of storage and computation time if the number of variables increases. For this reason, there is code to manipulate polynomials in a sparse representation.

Sparse polynomials are represented as dictionaries.

diofant.polys.rings.ring(symbols, domain, order=<diofant.polys.orderings.LexOrder object>)[source]

Construct a polynomial ring returning (ring, x_1, ..., x_n).

Parameters:
  • symbols (str, Symbol/Expr or sequence of str, Symbol/Expr (non-empty))

  • domain (Domain or coercible)

  • order (Order or coercible, optional, defaults to lex)

Examples

>>> R, x, y, z = ring('x y z', ZZ)
>>> R
ZZ[x,y,z]
>>> x + y + z
x + y + z
class diofant.polys.rings.PolyElement[source]

Represent a polynomial in a multivariate polynomial ring.

A polynomial is mutable, until its hash is computed, e.g. for using an instance as a dictionary key.

See also

PolynomialRing

__add__(other)[source]

Add two polynomials.

__eq__(other)[source]

Equality test for polynomials.

Examples

>>> _, x, y = ring('x y', ZZ)
>>> p1 = (x + y)**2 + (x - y)**2
>>> p1 == 4*x*y
False
>>> p1 == 2*(x**2 + y**2)
True
__getitem__(monom, /)[source]

Return the coefficient for the given monomial.

Parameters:

monom (Monomial or PolyElement (with is_monomial = True) or 1)

Examples

>>> _, x, y, z = ring('x y z', ZZ)
>>> f = 3*x**2*y - x*y*z + 7*z**3 + 23
>>> f[x**2*y]
3
>>> f[x*y]
0
>>> f[1]
23
__mul__(other)[source]

Multiply two polynomials.

__pow__(n, mod=None)[source]

Raise polynomial to power \(n\).

__radd__(other)[source]

Add two polynomials.

__rmul__(other)[source]

Multiply two polynomials.

__rsub__(other)[source]

Substract self from other, with other convertible to the coefficient domain.

__setitem__(monom, coeff, /)[source]

Set the coefficient for the given monomial.

Parameters:
  • monom (Monomial or PolyElement (with is_monomial = True) or 1)

  • coeff (DomainElement)

Examples

>>> _, x, y = ring('x y', ZZ)
>>> p = (x + y)**2
>>> p1 = p.copy()
>>> p2 = p
>>> p[x*y] = 0
>>> p1
x**2 + 2*x*y + y**2
>>> p2
x**2 + y**2
>>> _ = hash(p)
>>> p[x*y] = 1
Traceback (most recent call last):
...
RuntimeError: Polynomial x**2 + y**2 can't be modified
__sub__(other)[source]

Subtract polynomial other from self.

__weakref__

list of weak references to the object (if defined)

cancel(g, include=True)[source]

Cancel common factors in a rational function f/g.

Examples

>>> _, x, y = ring('x y', ZZ)
>>> (2*x**2 - 2).cancel(x**2 - 2*x + 1)
(2*x + 2, x - 1)
compose(x, a=None)[source]

Computes the functional composition.

content()[source]

Returns GCD of polynomial’s coefficients.

copy()[source]

Return a shallow copy of self.

degree(x=0)[source]

The leading degree in x or the main variable.

Note that the degree of 0 is negative floating-point infinity.

diff(x=0, m=1)[source]

Computes partial derivative in x.

Examples

>>> _, x, y = ring('x y', ZZ)
>>> p = x + x**2*y**3
>>> p.diff(x)
2*x*y**3 + 1
discriminant()[source]

Computes discriminant of a polynomial.

div(fv)[source]

Division algorithm for multivariate polynomials.

Parameters:

fv (sequence of PolyElement’s) – List of divsors.

Returns:

(qv, r) (tuple) – Where qv is the sequence of quotients and r is the remainder.

Notes

For multivariate polynomials the remainder is not uniquely determined, unless divisors form a Gröbner basis.

Examples

>>> _, x, y = ring('x y', ZZ)
>>> f = x**2*y
>>> f1, f2 = x**2 - y, x*y - 1
>>> f.div([f1, f2])
([y, 0], y**2)
>>> f.div([f2, f1])
([x, 0], x)
>>> g1, g2 = x - y**2, y**3 - 1
>>> f.div([g1, g2])[1] == f.div([g2, g1])[1]
True

References

gcdex(other)[source]

Extended Euclidean algorithm in \(F[x]\).

Returns (s, t, h) such that h = gcd(self, other) and s*self + t*other = h.

Examples

>>> _, x = ring('x', QQ)
>>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15
>>> g = x**3 + x**2 - 4*x - 4
>>> f.gcdex(g)
(-1/5*x + 3/5, 1/5*x**2 - 6/5*x + 2, x + 1)
half_gcdex(other)[source]

Half extended Euclidean algorithm in \(F[x]\).

Returns (s, h) such that h = gcd(self, other) and s*self = h (mod other).

Examples

>>> _, x = ring('x', QQ)
>>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15
>>> g = x**3 + x**2 - 4*x - 4
>>> f.half_gcdex(g)
(-1/5*x + 3/5, x + 1)
integrate(x=0, m=1)[source]

Computes indefinite integral in x.

leading_expv(order=None)[source]

Leading monomial tuple according to the monomial ordering.

Examples

>>> _, x, y, z = ring('x y z', ZZ)
>>> p = x**4 + x**3*y + x**2*z**2 + z**7
>>> p.leading_expv()
(4, 0, 0)
leading_term(order=None)[source]

Leading term as a polynomial element.

Examples

>>> _, x, y = ring('x y', ZZ)
>>> (3*x*y + y**2).leading_term()
3*x*y
monic()[source]

Divides all coefficients by the leading coefficient.

prem(other)[source]

Polynomial pseudo-remainder.

Examples

>>> _, x, y = ring('x y', ZZ)
>>> (x**2 + x*y).prem(2*x + 2)
-4*y + 4

References

primitive()[source]

Returns content and a primitive polynomial.

resultant(other, includePRS=False)[source]

Computes resultant of two polynomials in \(K[X]\).

Examples

>>> _, x, y = ring('x y', ZZ)
>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9
>>> f.resultant(g)
-3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16
subresultants(other)[source]

Computes subresultant PRS of two polynomials in \(K[X]\).

Examples

>>> _, x, y = ring('x y', ZZ)
>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9
>>> a = 3*x*y**4 + y**3 - 27*y + 4
>>> b = -3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16
>>> f.subresultants(g) == [f, g, a, b]
True
tail_degree(x=0)[source]

The tail degree in x or the main variable.

Note that the degree of 0 is negative floating-point infinity.

total_degree()[source]

Returns the total degree.

class diofant.polys.univar.UnivarPolyElement[source]

Element of univariate distributed polynomial ring.

decompose()[source]

Compute functional decomposition of f in K[x].

Given a univariate polynomial f with coefficients in a field of characteristic zero, returns list [f_1, f_2, ..., f_n], where:

f = f_1 o f_2 o ... f_n = f_1(f_2(... f_n))

and f_2, ..., f_n are monic and homogeneous polynomials of at least second degree.

Unlike factorization, complete functional decompositions of polynomials are not unique, consider examples:

  1. f o g = f(x + b) o (g - b)

  2. x**n o x**m = x**m o x**n

  3. T_n o T_m = T_m o T_n

where T_n and T_m are Chebyshev polynomials.

Examples

>>> _, x = ring('x', ZZ)
>>> (x**4 - 2*x**3 + x**2).decompose()
[x**2, x**2 - x]

References

sturm()[source]

Computes the Sturm sequence of f in F[x].

Given a univariate, square-free polynomial f(x) returns the associated Sturm sequence (see e.g. [DST88]) f_0(x), ..., f_n(x) defined by:

f_0(x), f_1(x) = f(x), f'(x)
f_n = -rem(f_{n-2}(x), f_{n-1}(x))

Examples

>>> _, x = ring('x', QQ)
>>> (x**3 - 2*x**2 + x - 3).sturm()
[x**3 - 2*x**2 + x - 3, 3*x**2 - 4*x + 1, 2/9*x + 25/9, -2079/4]

Polynomial factorization algorithms

Many variants of Euclid’s algorithm:

Classical remainder sequence

Let \(K\) be a field, and consider the ring \(K[X]\) of polynomials in a single indeterminate \(X\) with coefficients in \(K\). Given two elements \(f\) and \(g\) of \(K[X]\) with \(g\neq 0\) there are unique polynomials \(q\) and \(r\) such that \(f = qg + r\) and \(\deg(r) < \deg(g)\) or \(r = 0\). They are denoted by \(\mathrm{quo}(f,g)\) (quotient) and \(\mathrm{rem}(f,g)\) (remainder), so we have the division identity

\[f = \mathrm{quo}(f,g)g + \mathrm{rem}(f,g).\]

It follows that every ideal \(I\) of \(K[X]\) is a principal ideal, generated by any element \(\neq 0\) of minimum degree (assuming \(I\) non-zero). In fact, if \(g\) is such a polynomial and \(f\) is any element of \(I\), \(\mathrm{rem}(f,g)\) belongs to \(I\) as a linear combination of \(f\) and \(g\), hence must be zero; therefore \(f\) is a multiple of \(g\).

Using this result it is possible to find a greatest common divisor (gcd) of any polynomials \(f,g,\ldots\) in \(K[X]\). If \(I\) is the ideal formed by all linear combinations of the given polynomials with coefficients in \(K[X]\), and \(d\) is its generator, then every common divisor of the polynomials also divides \(d\). On the other hand, the given polynomials are multiples of the generator \(d\); hence \(d\) is a gcd of the polynomials, denoted \(\mathrm{gcd}(f,g,\ldots)\).

An algorithm for the gcd of two polynomials \(f\) and \(g\) in \(K[X]\) can now be obtained as follows. By the division identity, \(r = \mathrm{rem}(f,g)\) is in the ideal generated by \(f\) and \(g\), as well as \(f\) is in the ideal generated by \(g\) and \(r\). Hence the ideals generated by the pairs \((f,g)\) and \((g,r)\) are the same. Set \(f_0 = f\), \(f_1 = g\), and define recursively \(f_i = \mathrm{rem}(f_{i-2},f_{i-1})\) for \(i\ge 2\). The recursion ends after a finite number of steps with \(f_{k+1}=0\), since the degrees of the polynomials are strictly decreasing. By the above remark, all the pairs \((f_{i-1},f_i)\) generate the same ideal. In particular, the ideal generated by \(f\) and \(g\) is generated by \(f_k\) alone as \(f_{k+1} = 0\). Hence \(d = f_k\) is a gcd of \(f\) and \(g\).

The sequence of polynomials \(f_0\), \(f_1,\ldots, f_k\) is called the Euclidean polynomial remainder sequence determined by \((f,g)\) because of the analogy with the classical Euclidean algorithm for the gcd of natural numbers.

The algorithm may be extended to obtain an expression for \(d\) in terms of \(f\) and \(g\) by using the full division identities to write recursively each \(f_i\) as a linear combination of \(f\) and \(g\). This leads to an equation

\[d = uf + vg\qquad (u,v \in K[X])\]

analogous to Bézout’s identity in the case of integers.

Simplified remainder sequences

Assume, as is usual, that the coefficient field \(K\) is the field of fractions of an integral domain \(A\). In this case the coefficients (numerators and denominators) of the polynomials in the Euclidean remainder sequence tend to grow very fast.

If \(A\) is a unique factorization domain, the coefficients may be reduced by cancelling common factors of numerators and denominators. Further reduction is possible noting that a gcd of polynomials in \(K[X]\) is not unique: it may be multiplied by any (non-zero) constant factor.

Any polynomial \(f\) in \(K[X]\) can be simplified by extracting the denominators and common factors of the numerators of its coefficients. This yields the representation \(f = cF\) where \(c\in K\) is the content of \(f\) and \(F\) is a primitive polynomial, i.e., a polynomial in \(A[X]\) with coprime coefficients.

It is possible to start the algorithm by replacing the given polynomials \(f\) and \(g\) with their primitive parts. This will only modify \(\mathrm{rem}(f,g)\) by a constant factor. Replacing it with its primitive part and continuing recursively we obtain all the primitive parts of the polynomials in the Euclidean remainder sequence, including the primitive \(\mathrm{gcd}(f,g)\).

This sequence is the primitive polynomial remainder sequence. It is an example of general polynomial remainder sequences where the computed remainders are modified by constant multipliers (or divisors) in order to simplify the results.

Subresultant sequence

The coefficients of the primitive polynomial sequence do not grow exceedingly, but the computation of the primitive parts requires extra processing effort. Besides, the method only works with fraction fields of unique factorization domains, excluding, for example, the general number fields.

Collins [Col67] realized that the so-called subresultant polynomials of a pair of polynomials also form a generalized remainder sequence. The coefficients of these polynomials are expressible as determinants in the coefficients of the given polynomials. Hence (the logarithm of) their size only grows linearly. In addition, if the coefficients of the given polynomials are in the subdomain \(A\), so are those of the subresultant polynomials. This means that the subresultant sequence is comparable to the primitive remainder sequence without relying on unique factorization in \(A\).

To see how subresultants are associated with remainder sequences recall that all polynomials \(h\) in the sequence are linear combinations of the given polynomials \(f\) and \(g\)

\[h = uf+vg\]

with polynomials \(u\) and \(v\) in \(K[X]\). Moreover, as is seen from the extended Euclidean algorithm, the degrees of \(u\) and \(v\) are relatively low, with limited growth from step to step.

Let \(n = \deg(f)\), and \(m = \deg(g)\), and assume \(n\ge m\). If \(\deg(h) = j < m\), the coefficients of the powers \(X^k\) (\(k > j\)) in the products \(uf\) and \(vg\) cancel each other. In particular, the products must have the same degree, say, \(l\). Then \(\deg(u) = l - n\) and \(\deg(v) = l - m\) with a total of \(2l -n - m + 2\) coefficients to be determined.

On the other hand, the equality \(h = uf + vg\) implies that \(l - j\) linear combinations of the coefficients are zero, those associated with the powers \(X^i\) (\(j < i \leq l\)), and one has a given non-zero value, namely the leading coefficient of \(h\).

To satisfy these \(l - j + 1\) linear equations the total number of coefficients to be determined cannot be lower than \(l - j + 1\), in general. This leads to the inequality \(l \ge n + m - j - 1\). Taking \(l = n + m - j - 1\), we obtain \(\deg(u) = m - j - 1\) and \(\deg(v) = n - j - 1\).

In the case \(j = 0\) the matrix of the resulting system of linear equations is the Sylvester matrix \(S(f,g)\) associated to \(f\) and \(g\), an \((n+m)\times (n+m)\) matrix with coefficients of \(f\) and \(g\) as entries. Its determinant is the resultant \(\mathrm{res}(f,g)\) of the pair \((f,g)\). It is non-zero if and only if \(f\) and \(g\) are relatively prime.

For any \(j\) in the interval from \(0\) to \(m\) the matrix of the linear system is an \((n+m-2j)\times (n+m-2j)\) submatrix of the Sylvester matrix. Its determinant \(s_j(f,g)\) is called the \(j\) th scalar subresultant of \(f\) and \(g\).

If \(s_j(f,g)\) is not zero, the associated equation \(h = uf + vg\) has a unique solution where \(\deg(h) = j\) and the leading coefficient of \(h\) has any given value; the one with leading coefficient \(s_j(f,g)\) is the \(j\) th subresultant polynomial or, briefly, subresultant of the pair \((f,g)\), and denoted \(S_j(f,g)\). This choice guarantees that the remainining coefficients are also certain subdeterminants of the Sylvester matrix. In particular, if \(f\) and \(g\) are in \(A[X]\), so is \(S_j(f,g)\) as well. This construction of subresultants applies to any \(j\) between \(0\) and \(m\) regardless of the value of \(s_j(f,g)\); if it is zero, then \(\deg(S_j(f,g)) < j\).

The properties of subresultants are as follows. Let \(n_0 = \deg(f)\), \(n_1 = \deg(g)\), \(n_2, \ldots, n_k\) be the decreasing sequence of degrees of polynomials in a remainder sequence. Let \(0 \le j \le n_1\); then

  • \(s_j(f,g)\ne 0\) if and only if \(j = n_i\) for some \(i\).

  • \(S_j(f,g)\ne 0\) if and only if \(j = n_i\) or \(j = n_i - 1\) for some \(i\).

Normally, \(n_{i-1} - n_i = 1\) for \(1 < i \le k\). If \(n_{i-1} - n_i > 1\) for some \(i\) (the abnormal case), then \(S_{n_{i-1}-1}(f,g)\) and \(S_{n_i}(f,g)\) are constant multiples of each other. Hence either one could be included in the polynomial remainder sequence. The former is given by smaller determinants, so it is expected to have smaller coefficients.

Collins defined the subresultant remainder sequence by setting

\[f_i = S_{n_{i-1}-1}(f,g) \qquad (2\le i \le k).\]

In the normal case, these are the same as the \(S_{n_i}(f,g)\). He also derived expressions for the constants \(\gamma_i\) in the remainder formulas

\[\gamma_i f_i = \mathrm{rem}(f_{i-2},f_{i-1})\]

in terms of the leading coefficients of \(f_1,\ldots,f_{i-1}\), working in the field \(K\).

Brown and Traub [BT71] later developed a recursive procedure for computing the coefficients \(\gamma_i\). Their algorithm deals with elements of the domain \(A\) exclusively (assuming \(f,g\in A[X]\)). However, in the abnormal case there was a problem, a division in \(A\) which could only be conjectured to be exact.

This was subsequently justified by Brown [Bro78] who showed that the result of the division is, in fact, a scalar subresultant. More specifically, the constant appearing in the computation of \(f_i\) is \(s_{n_{i-2}}(f,g)\) (Theorem 3). The implication of this discovery is that the scalar subresultants are computed as by-products of the algorithm, all but \(s_{n_k}(f,g)\) which is not needed after finding \(f_{k+1} = 0\). Completing the last step we obtain all non-zero scalar subresultants, including the last one which is the resultant if this does not vanish.

Polynomial factorization in characteristic zero:

Polynomial factorization routines in characteristic zero.

Gröbner basis algorithms

Gröbner bases can be used to answer many problems in computational commutative algebra. Their computation in rather complicated, and very performance-sensitive. We present here various low-level implementations of Gröbner basis computation algorithms; please see the previous section of the manual for usage.

Gröbner bases algorithms.

diofant.polys.groebnertools.buchberger(f, ring)[source]

Computes Gröbner basis for a set of polynomials in \(K[X]\).

Given a set of multivariate polynomials \(F\), finds another set \(G\), such that Ideal \(F = Ideal G\) and \(G\) is a reduced Gröbner basis.

The resulting basis is unique and has monic generators if the ground domains is a field. Otherwise the result is non-unique but Gröbner bases over e.g. integers can be computed (if the input polynomials are monic).

Gröbner bases can be used to choose specific generators for a polynomial ideal. Because these bases are unique you can check for ideal equality by comparing the Gröbner bases. To see if one polynomial lies in an ideal, divide by the elements in the base and see if the remainder vanishes.

They can also be used to solve systems of polynomial equations as, by choosing lexicographic ordering, you can eliminate one variable at a time, provided that the ideal is zero-dimensional (finite number of solutions).

References

Notes

Used an improved version of Buchberger’s algorithm as presented in [BW93].

diofant.polys.groebnertools.cp_key(c, ring)[source]

Key for comparing critical pairs.

diofant.polys.groebnertools.critical_pair(f, g, ring)[source]

Compute the critical pair corresponding to two labeled polynomials.

A critical pair is a tuple (um, f, vm, g), where um and vm are terms such that um * f - vm * g is the S-polynomial of f and g (so, wlog assume um * f > vm * g). For performance sake, a critical pair is represented as a tuple (Sign(um * f), um, f, Sign(vm * g), vm, g), since um * f creates a new, relatively expensive object in memory, whereas Sign(um * f) and um are lightweight and f (in the tuple) is a reference to an already existing object in memory.

diofant.polys.groebnertools.f5_reduce(f, B)[source]

F5-reduce a labeled polynomial f by B.

Continously searches for non-zero labeled polynomial h in B, such that the leading term lt_h of h divides the leading term lt_f of f and Sign(lt_h * h) < Sign(f). If such a labeled polynomial h is found, f gets replaced by f - lt_f / lt_h * h. If no such h can be found or f is 0, f is no further F5-reducible and f gets returned.

A polynomial that is reducible in the usual sense need not be F5-reducible, e.g.:

>>> _, x, y, z = ring('x y z', QQ, lex)
>>> f = lbp(sig(Monomial((1, 1, 1)), 4), x, 3)
>>> g = lbp(sig(Monomial((0, 0, 0)), 2), x, 2)
>>> Polyn(f).div([Polyn(g)])[1]
0
>>> f5_reduce(f, [g])
(((1, 1, 1), 4), x, 3)
diofant.polys.groebnertools.f5b(F, ring)[source]

Computes a reduced Gröbner basis for the ideal generated by F.

f5b is an implementation of the F5B algorithm by Yao Sun and Dingkang Wang. Similarly to Buchberger’s algorithm, the algorithm proceeds by computing critical pairs, computing the S-polynomial, reducing it and adjoining the reduced S-polynomial if it is not 0.

Unlike Buchberger’s algorithm, each polynomial contains additional information, namely a signature and a number. The signature specifies the path of computation (i.e. from which polynomial in the original basis was it derived and how), the number says when the polynomial was added to the basis. With this information it is (often) possible to decide if an S-polynomial will reduce to 0 and can be discarded.

Optimizations include: Reducing the generators before computing a Gröbner basis, removing redundant critical pairs when a new polynomial enters the basis and sorting the critical pairs and the current basis.

Once a Gröbner basis has been found, it gets reduced.

References

diofant.polys.groebnertools.groebner(seq, ring, method=None)[source]

Computes Gröbner basis for a set of polynomials in \(K[X]\).

Wrapper around the (default) improved Buchberger and the other algorithms for computing Gröbner bases. The choice of algorithm can be changed via method argument, where method can be either buchberger or f5b. Default value is determined by setup().

diofant.polys.groebnertools.groebner_gcd(f, g)[source]

Computes GCD of two polynomials using Gröbner bases.

diofant.polys.groebnertools.groebner_lcm(f, g)[source]

Computes LCM of two polynomials using Gröbner bases.

The LCM is computed as the unique generator of the intersection of the two ideals generated by \(f\) and \(g\). The approach is to compute a Gröbner basis with respect to lexicographic ordering of \(t*f\) and \((1 - t)*g\), where \(t\) is an unrelated variable and then filtering out the solution that doesn’t contain \(t\).

References

diofant.polys.groebnertools.is_groebner(G)[source]

Check if G is a Gröbner basis.

diofant.polys.groebnertools.is_minimal(G, ring)[source]

Checks if G is a minimal Gröbner basis.

diofant.polys.groebnertools.is_rewritable_or_comparable(sign, num, B)[source]

Check if a labeled polynomial is redundant by checking if its signature and number imply rewritability or comparability.

(sign, num) is comparable if there exists a labeled polynomial h in B, such that sign[1] (the index) is less than Sign(h)[1] and sign[0] is divisible by the leading monomial of h.

(sign, num) is rewritable if there exists a labeled polynomial h in B, such thatsign[1] is equal to Sign(h)[1], num < Num(h) and sign[0] is divisible by Sign(h)[0].

diofant.polys.groebnertools.lbp_cmp(f, g)[source]

Compare two labeled polynomials.

f < g iff
  • Sign(f) < Sign(g)

or
  • Sign(f) == Sign(g) and Num(f) > Num(g)

f > g otherwise

diofant.polys.groebnertools.lbp_key(f)[source]

Key for comparing two labeled polynomials.

diofant.polys.groebnertools.lbp_mul_term(f, cx)[source]

Multiply a labeled polynomial with a term.

The product of a labeled polynomial (s, p, k) by a monomial is defined as (m * s, m * p, k).

diofant.polys.groebnertools.lbp_sub(f, g)[source]

Subtract labeled polynomial g from f.

The signature and number of the difference of f and g are signature and number of the maximum of f and g, w.r.t. lbp_cmp.

diofant.polys.groebnertools.matrix_fglm(F, ring, O_to)[source]

Converts the reduced Gröbner basis F of a zero-dimensional ideal w.r.t. O_from to a reduced Gröbner basis w.r.t. O_to.

References

diofant.polys.groebnertools.red_groebner(G, ring)[source]

Compute reduced Gröbner basis.

Selects a subset of generators, that already generate the ideal and computes a reduced Gröbner basis for them.

References

diofant.polys.groebnertools.s_poly(cp)[source]

Compute the S-polynomial of a critical pair.

The S-polynomial of a critical pair cp is cp[1] * cp[2] - cp[4] * cp[5].

diofant.polys.groebnertools.sig_cmp(u, v, order)[source]

Compare two signatures by extending the term order to K[X]^n.

u < v iff
  • the index of v is greater than the index of u

or
  • the index of v is equal to the index of u and u[0] < v[0] w.r.t. order

u > v otherwise

diofant.polys.groebnertools.sig_key(s, order)[source]

Key for comparing two signatures.

s = (m, k), t = (n, l)

s < t iff [k > l] or [k == l and m < n] s > t otherwise

diofant.polys.groebnertools.sig_mult(s, m)[source]

Multiply a signature by a monomial.

The product of a signature (m, i) and a monomial n is defined as (m * t, i).

diofant.polys.groebnertools.spoly(p1, p2)[source]

Compute LCM(LM(p1), LM(p2))/LM(p1)*p1 - LCM(LM(p1), LM(p2))/LM(p2)*p2.

This is the S-poly, provided p1 and p2 are monic

Algebraic number fields

diofant.polys.numberfields.minpoly_groebner(ex, x, domain)[source]

Computes the minimal polynomial of an algebraic number using Gröbner bases

Examples

>>> minimal_polynomial(sqrt(2) + 1, method='groebner')(x)
x**2 - 2*x - 1

References

Factorization over algebraic number fields

diofant.polys.factorization_alg_field._alpha_to_z(f, ring)[source]

Change the representation of a polynomial over \(\mathbb Q(\alpha)\) by replacing the algebraic element \(\alpha\) by a new variable \(z\).

Parameters:
  • f (PolyElement) – polynomial in \(\mathbb Q(\alpha)[x_0, \ldots, x_n]\)

  • ring (PolynomialRing) – the polynomial ring \(\mathbb Q[x_0, \ldots, x_n, z]\)

Returns:

f_ (PolyElement) – polynomial in \(\mathbb Q[x_0, \ldots, x_n, z]\)

diofant.polys.factorization_alg_field._denominator(f)[source]

Compute the denominator \(\mathrm{den}(f)\) of a polynomial \(f\) over \(\mathbb Q\), i.e. the smallest integer such that \(\mathrm{den}(f) f\) is a polynomial over \(\mathbb Z\).

diofant.polys.factorization_alg_field._diophantine(F, c, A, d, minpoly, p)[source]

Solve multivariate Diophantine equations over \(\mathbb Z_p[z]/(\mu(z))\).

diofant.polys.factorization_alg_field._diophantine_univariate(F, m, minpoly, p)[source]

Solve univariate Diophantine equations of the form

\[\sum_{f \in F} \left( h_f(x) \cdot \prod_{g \in F \setminus \lbrace f \rbrace } g(x) \right) = x^m\]

over \(\mathbb Z_p[z]/(\mu(z))\).

diofant.polys.factorization_alg_field._distinct_prime_divisors(S, domain)[source]

Find pairwise coprime divisors of all elements of a given list \(S\) of integers. If this fails, None is returned.

References

  • [JM09], Algorithm 4

diofant.polys.factorization_alg_field._extended_euclidean_algorithm(f, g, minpoly, p)[source]

Extended Euclidean Algorithm for univariate polynomials over \(\mathbb Z_p[z]/(\mu(z))\).

Returns \(s, t, h\), where \(h\) is the GCD of \(f\) and \(g\) and \(sf + tg = h\).

diofant.polys.factorization_alg_field._factor(f)[source]

Factor a multivariate polynomial \(f\), which is squarefree and primitive in \(x_0\), in \(\mathbb Q(\alpha)[x_0, \ldots, x_n]\).

References

diofant.polys.factorization_alg_field._hensel_lift(f, H, LC, A, minpoly, p)[source]

Parallel Hensel lifting algorithm over \(\mathbb Z_p[z]/(\mu(z))\).

Parameters:
  • f (PolyElement) – squarefree polynomial in \(\mathbb Z[x_0, \ldots, x_n, z]\)

  • H (list of PolyElement objects) – monic univariate factors of \(f(x_0, A)\) in \(\mathbb Z[x_0, z]\)

  • LC (list of PolyElement objects) – true leading coefficients of the irreducible factors of \(f\)

  • A (list of Integer objects) – the evaluation point \([a_1, \ldots, a_n]\)

  • p (Integer) – prime number

Returns:

pfactors (list of PolyElement objects) – irreducible factors of \(f\) modulo \(p\)

diofant.polys.factorization_alg_field._leading_coeffs(f, U, gamma, lcfactors, A, D, denoms, divisors)[source]

Compute the true leading coefficients in \(x_0\) of the irreducible factors of a polynomial \(f\).

If this fails, None is returned.

Parameters:
  • f (PolyElement) – squarefree polynomial in \(Z[x_0, \ldots, x_n, z]\)

  • U (list of PolyElement objects) – monic univariate factors of \(f(x_0, A)\) in \(\mathbb Q(\alpha)[x_0]\)

  • gamma (Integer) – integer content of \(\mathrm{lc}_{x_0}(f)\)

  • lcfactors (list of (PolyElement, Integer) objects) – factorization of \(\mathrm{lc}_{x_0}(f)\) in \(\mathbb Z[x_1, \ldots, x_n, z]\)

  • A (list of Integer objects) – the evaluation point \([a_1, \ldots, a_n]\)

  • D (Integer) – integral multiple of the defect of \(\mathbb Q(\alpha)\)

  • denoms (list of Integer objects) – denominators of \(\frac 1 {l(A)}\) for \(l\) in lcfactors

  • divisors (list of Integer objects) – pairwise coprime divisors of all elements of denoms

Returns:

  • f (PolyElement) – possibly updated polynomial \(f\)

  • lcs (list of PolyElement objects) – true leading coefficients of the irreducible factors of \(f\)

  • U_ (list of PolyElement objects) – list of possibly updated monic associates of the univariate factors \(U\)

References

diofant.polys.factorization_alg_field._monic_associate(f, ring)[source]

Compute the monic associate of a polynomial \(f\) over \(\mathbb Q(\alpha)\), which is defined as

\[\mathrm{den}\left( \frac 1 {\mathrm{lc}(f)} f \right) \cdot \frac 1 {\mathrm{lc}(f)} f.\]

The result is a polynomial in \(\mathbb Z[x_0, \ldots, x_n, z]\).

diofant.polys.factorization_alg_field._padic_lift(f, pfactors, lcs, B, minpoly, p)[source]

Lift the factorization of a polynomial over \(\mathbb Z_p[z]/(\mu(z))\) to a factorization over \(\mathbb Z_{p^m}[z]/(\mu(z))\), where \(p^m \geq B\).

If this fails, None is returned.

Parameters:
  • f (PolyElement) – squarefree polynomial in \(\mathbb Z[x_0, \ldots, x_n, z]\)

  • pfactors (list of PolyElement objects) – irreducible factors of \(f\) modulo \(p\)

  • lcs (list of PolyElement objects) – true leading coefficients in \(x_0\) of the irreducible factors of \(f\)

  • B (Integer) – heuristic numerical bound on the size of the largest integer coefficient in the irreducible factors of \(f\)

  • minpoly (PolyElement) – minimal polynomial \(\mu\) of \(\alpha\) over \(\mathbb Q\)

  • p (Integer) – prime number

Returns:

H (list of PolyElement objects) – factorization of \(f\) modulo \(p^m\), where \(p^m \geq B\)

References

diofant.polys.factorization_alg_field._sqf_p(f, minpoly, p)[source]

Return True if nonzero \(f\) is square-free in \(\mathbb Z_p[z]/(\mu(z))[x]\).

diofant.polys.factorization_alg_field._subs_ground(f, A)[source]

Substitute variables in the coefficients of a polynomial \(f\) over a PolynomialRing.

diofant.polys.factorization_alg_field._test_evaluation_points(f, gamma, lcfactors, A, D)[source]

Test if an evaluation point is suitable for _factor.

If it is not, None is returned.

Parameters:
  • f (PolyElement) – squarefree polynomial in \(\mathbb Z[x_0, \ldots, x_n, z]\)

  • gamma (Integer) – leading coefficient of \(f\) in \(\mathbb Z\)

  • lcfactors (list of (PolyElement, Integer) objects) – factorization of \(\mathrm{lc}_{x_0}(f)\) in \(\mathbb Z[x_1, \ldots, x_n, z]\)

  • A (list of Integer objects) – the evaluation point \([a_1, \ldots, a_n]\)

  • D (Integer) – integral multiple of the defect of \(\mathbb Q(\alpha)\)

Returns:

  • fA (PolyElement) – \(f\) evaluated at \(A\), i.e. \(f(x_0, A)\)

  • denoms (list of Integer objects) – the denominators of \(\frac 1 {l(A)}\) for \(l\) in lcfactors

  • divisors (list of Integer objects) – pairwise coprime divisors of all elements of denoms

References

See also

_factor

diofant.polys.factorization_alg_field._test_prime(f, A, minpoly, p)[source]

Test if a prime number is suitable for _factor.

See also

_factor

diofant.polys.factorization_alg_field._z_to_alpha(f, ring)[source]

Change the representation of a polynomial in \(\mathbb Q[x_0, \ldots, x_n, z]\) by replacing the variable \(z\) by the algebraic element \(\alpha\) of the given ring \(\mathbb Q(\alpha)[x_0, \ldots, x_n]\).

Parameters:
  • f (PolyElement) – polynomial in \(\mathbb Q[x_0, \ldots, x_n, z]\)

  • ring (PolynomialRing) – the polynomial ring \(\mathbb Q(\alpha)[x_0, \ldots, x_n]\)

Returns:

f_ (PolyElement) – polynomial in \(\mathbb Q(\alpha)[x_0, \ldots, x_n]\)

diofant.polys.factorization_alg_field.efactor(f)[source]

Factor multivariate polynomial \(f\) over algebraic number fields.

References

diofant.polys.factorization_alg_field.trager(f)[source]

Factor multivariate polynomial \(f\) over algebraic number fields, using classical Trager algorithm.

References

Modular GCD

diofant.polys.modulargcd._chinese_remainder_reconstruction(hp, hq, p, q)[source]

Construct a polynomial \(h_{pq}\) in \(\mathbb{Z}_{p q}[x_0, \ldots, x_{k-1}]\) such that

\[ \begin{align}\begin{aligned}h_{pq} = h_p \; \mathrm{mod} \, p\\h_{pq} = h_q \; \mathrm{mod} \, q\end{aligned}\end{align} \]

for relatively prime integers \(p\) and \(q\) and polynomials \(h_p\) and \(h_q\) in \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\) and \(\mathbb{Z}_q[x_0, \ldots, x_{k-1}]\) respectively.

The coefficients of the polynomial \(h_{pq}\) are computed with the Chinese Remainder Theorem. The symmetric representation in \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\), \(\mathbb{Z}_q[x_0, \ldots, x_{k-1}]\) and \(\mathbb{Z}_{p q}[x_0, \ldots, x_{k-1}]\) is used.

Parameters:
  • hp (PolyElement) – multivariate integer polynomial with coefficients in \(\mathbb{Z}_p\)

  • hq (PolyElement) – multivariate integer polynomial with coefficients in \(\mathbb{Z}_q\)

  • p (Integer) – modulus of \(h_p\), relatively prime to \(q\)

  • q (Integer) – modulus of \(h_q\), relatively prime to \(p\)

Examples

>>> _, x, y = ring('x y', ZZ)
>>> p = 3
>>> q = 5
>>> hp = x**3*y - x**2 - 1
>>> hq = -x**3*y - 2*x*y**2 + 2
>>> hpq = _chinese_remainder_reconstruction(hp, hq, p, q)
>>> hpq
4*x**3*y + 5*x**2 + 3*x*y**2 + 2
>>> hpq.trunc_ground(p) == hp
True
>>> hpq.trunc_ground(q) == hq
True
>>> _, x, y, z = ring('x y z', ZZ)
>>> p = 6
>>> q = 5
>>> hp = 3*x**4 - y**3*z + z
>>> hq = -2*x**4 + z
>>> hpq = _chinese_remainder_reconstruction(hp, hq, p, q)
>>> hpq
3*x**4 + 5*y**3*z + z
>>> hpq.trunc_ground(p) == hp
True
>>> hpq.trunc_ground(q) == hq
True
diofant.polys.modulargcd._div(f, g, minpoly, p)[source]

Division with remainder for univariate polynomials over \(\mathbb Z_p[z]/(\mu(z))\).

diofant.polys.modulargcd._euclidean_algorithm(f, g, minpoly, p)[source]

Compute the monic GCD of two univariate polynomials in \(\mathbb{Z}_p[z]/(\check m_{\alpha}(z))[x]\) with the Euclidean Algorithm.

In general, \(\check m_{\alpha}(z)\) is not irreducible, so it is possible that some leading coefficient is not invertible modulo \(\check m_{\alpha}(z)\). In that case None is returned.

Parameters:
  • f, g (PolyElement) – polynomials in \(\mathbb Z[x, z]\)

  • minpoly (PolyElement) – polynomial in \(\mathbb Z[z]\), not necessarily irreducible

  • p (Integer) – prime number, modulus of \(\mathbb Z_p\)

Returns:

h (PolyElement) – GCD of \(f\) and \(g\) in \(\mathbb Z[z, x]\) or None, coefficients are in \(\left[ -\frac{p-1} 2, \frac{p-1} 2 \right]\)

diofant.polys.modulargcd._evaluate_ground(f, i, a)[source]

Evaluate a polynomial \(f\) at \(a\) in the \(i\)-th variable of the ground domain.

diofant.polys.modulargcd._func_field_modgcd_m(f, g, minpoly)[source]

Compute the GCD of two polynomials in \(\mathbb Q(t_1, \ldots, t_k)[z]/(m_{\alpha}(z))[x]\) using a modular algorithm.

The algorithm computes the GCD of two polynomials \(f\) and \(g\) by calculating the GCD in \(\mathbb Z_p(t_1, \ldots, t_k)[z] / (\check m_{\alpha}(z))[x]\) for suitable primes \(p\) and the primitive associate \(\check m_{\alpha}(z)\) of \(m_{\alpha}(z)\). Then the coefficients are reconstructed with the Chinese Remainder Theorem and Rational Reconstruction. To compute the GCD over \(\mathbb Z_p(t_1, \ldots, t_k)[z] / (\check m_{\alpha})[x]\), the recursive subroutine _func_field_modgcd_p is used. To verify the result in \(\mathbb Q(t_1, \ldots, t_k)[z] / (m_{\alpha}(z))[x]\), a fraction free trial division is used.

Parameters:
  • f, g (PolyElement) – polynomials in \(\mathbb Z[t_1, \ldots, t_k][x, z]\)

  • minpoly (PolyElement) – irreducible polynomial in \(\mathbb Z[t_1, \ldots, t_k][z]\)

Returns:

h (PolyElement) – the primitive associate in \(\mathbb Z[t_1, \ldots, t_k][x, z]\) of the GCD of \(f\) and \(g\)

Examples

>>> _, x, z = ring('x z', ZZ)
>>> minpoly = (z**2 - 2).drop(0)
>>> f = x**2 + 2*x*z + 2
>>> g = x + z
>>> _func_field_modgcd_m(f, g, minpoly)
x + z
>>> D, t = ring('t', ZZ)
>>> _, x, z = ring('x z', D)
>>> minpoly = (z**2-3).drop(0)
>>> f = x**2 + (t + 1)*x*z + 3*t
>>> g = x*z + 3*t
>>> _func_field_modgcd_m(f, g, minpoly)
x + t*z

References

diofant.polys.modulargcd._func_field_modgcd_p(f, g, minpoly, p)[source]

Compute the GCD of two polynomials \(f\) and \(g\) in \(\mathbb Z_p(t_1, \ldots, t_k)[z]/(\check m_\alpha(z))[x]\).

The algorithm reduces the problem step by step by evaluating the polynomials \(f\) and \(g\) at \(t_k = a\) for suitable \(a \in \mathbb Z_p\) and then calls itself recursively to compute the GCD in \(\mathbb Z_p(t_1, \ldots, t_{k-1})[z]/(\check m_\alpha(z))[x]\). If these recursive calls are successful, the GCD over \(k\) variables is interpolated, otherwise the algorithm returns None. After interpolation, Rational Function Reconstruction is used to obtain the correct coefficients. If this fails, a new evaluation point has to be chosen, otherwise the desired polynomial is obtained by clearing denominators. The result is verified with a fraction free trial division.

Parameters:
  • f, g (PolyElement) – polynomials in \(\mathbb Z[t_1, \ldots, t_k][x, z]\)

  • minpoly (PolyElement) – polynomial in \(\mathbb Z[t_1, \ldots, t_k][z]\), not necessarily irreducible

  • p (Integer) – prime number, modulus of \(\mathbb Z_p\)

Returns:

h (PolyElement) – primitive associate in \(\mathbb Z[t_1, \ldots, t_k][x, z]\) of the GCD of the polynomials \(f\) and \(g\) or None, coefficients are in \(\left[ -\frac{p-1} 2, \frac{p-1} 2 \right]\)

References

diofant.polys.modulargcd._gf_gcdex(f, g, p)[source]

Extended Euclidean Algorithm for two univariate polynomials over \(\mathbb Z_p\).

Returns polynomials \(s, t\) and \(h\), such that \(h\) is the GCD of \(f\) and \(g\) and \(sf + tg = h \; \mathrm{mod} \, p\).

diofant.polys.modulargcd._interpolate(evalpoints, hpeval, ring, i, p, ground=False)[source]

Reconstruct a polynomial \(h_p\) in \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\) from a list of evaluation points in \(\mathbb{Z}_p\) and a list of polynomials in \(\mathbb{Z}_p[x_0, \ldots, x_{i-1}, x_{i+1}, \ldots, x_{k-1}]\), which are the images of \(h_p\) evaluated in the variable \(x_i\).

It is also possible to reconstruct a parameter of the ground domain, i.e. if \(h_p\) is a polynomial over \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\). In this case, one has to set ground=True.

Parameters:
  • evalpoints (list of Integer objects) – list of evaluation points in \(\mathbb{Z}_p\)

  • hpeval (list of PolyElement objects) – list of polynomials in (resp. over) \(\mathbb{Z}_p[x_0, \ldots, x_{i-1}, x_{i+1}, \ldots, x_{k-1}]\), images of \(h_p\) evaluated in the variable \(x_i\)

  • ring (PolynomialRing) – \(h_p\) will be an element of this ring

  • i (Integer) – index of the variable which has to be reconstructed

  • p (Integer) – prime number, modulus of \(h_p\)

  • ground (Boolean) – indicates whether \(x_i\) is in the ground domain, default is False

Returns:

hp (PolyElement) – interpolated polynomial in (resp. over) \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\)

diofant.polys.modulargcd._minpoly_from_dense(minpoly, ring)[source]

Change representation of the minimal polynomial from Poly to PolyElement for a given ring.

diofant.polys.modulargcd._modgcd_p(f, g, degbound, contbound)[source]

Compute the GCD of two polynomials in \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\).

The algorithm reduces the problem step by step by evaluating the polynomials \(f\) and \(g\) at \(x_{k-1} = a\) for suitable \(a \in \mathbb{Z}_p\) and then calls itself recursively to compute the GCD in \(\mathbb{Z}_p[x_0, \ldots, x_{k-2}]\). If these recursive calls are successful for enough evaluation points, the GCD in \(k\) variables is interpolated, otherwise the algorithm returns None. Every time a GCD or a content is computed, their degrees are compared with the bounds. If a degree greater then the bound is encountered, then the current call returns None and a new evaluation point has to be chosen. If at some point the degree is smaller, the correspondent bound is updated and the algorithm fails.

Parameters:
  • f (PolyElement) – multivariate polynomial with coefficients in \(\mathbb{Z}_p\)

  • g (PolyElement) – multivariate polynomial with coefficients in \(\mathbb{Z}_p\)

  • degbound (list of Integer objects) – degbound[i] is an upper bound for the degree of the GCD of \(f\) and \(g\) in the variable \(x_i\)

  • contbound (list of Integer objects) – contbound[i] is an upper bound for the degree of the content of the GCD in \(\mathbb{Z}_p[x_i][x_0, \ldots, x_{i-1}]\), contbound[0] is not used can therefore be chosen arbitrarily.

Returns:

h (PolyElement) – GCD of the polynomials \(f\) and \(g\) or None

References

diofant.polys.modulargcd._primitive_in_x0(f)[source]

Compute the content in \(x_0\) and the primitive part of a polynomial \(f\) in \(\mathbb Q(\alpha)[x_0, x_1, \ldots, x_{n-1}] \cong \mathbb Q(\alpha)[x_1, \ldots, x_{n-1}][x_0]\).

diofant.polys.modulargcd._rational_function_reconstruction(c, p, m)[source]

Reconstruct a rational function \(\frac a b\) in \(\mathbb Z_p(t)\) from

\[c = \frac a b \; \mathrm{mod} \, m,\]

where \(c\) and \(m\) are polynomials in \(\mathbb Z_p[t]\) and \(m\) has positive degree.

The algorithm is based on the Euclidean Algorithm. In general, \(m\) is not irreducible, so it is possible that \(b\) is not invertible modulo \(m\). In that case None is returned.

Parameters:
  • c (PolyElement) – univariate polynomial in \(\mathbb Z[t]\)

  • p (Integer) – prime number

  • m (PolyElement) – modulus, not necessarily irreducible

Returns:

frac (FracElement) – either \(\frac a b\) in \(\mathbb Z(t)\) or None

References

diofant.polys.modulargcd._rational_reconstruction_func_coeffs(hm, p, m, ring, k)[source]

Reconstruct every coefficient \(c_h\) of a polynomial \(h\) in \(\mathbb Z_p(t_k)[t_1, \ldots, t_{k-1}][x, z]\) from the corresponding coefficient \(c_{h_m}\) of a polynomial \(h_m\) in \(\mathbb Z_p[t_1, \ldots, t_k][x, z] \cong \mathbb Z_p[t_k][t_1, \ldots, t_{k-1}][x, z]\) such that

\[c_{h_m} = c_h \; \mathrm{mod} \, m,\]

where \(m \in \mathbb Z_p[t]\).

The reconstruction is based on the Euclidean Algorithm. In general, \(m\) is not irreducible, so it is possible that this fails for some coefficient. In that case None is returned.

Parameters:
  • hm (PolyElement) – polynomial in \(\mathbb Z[t_1, \ldots, t_k][x, z]\)

  • p (Integer) – prime number, modulus of \(\mathbb Z_p\)

  • m (PolyElement) – modulus, polynomial in \(\mathbb Z[t]\), not necessarily irreducible

  • ring (PolynomialRing) – \(\mathbb Z(t_k)[t_1, \ldots, t_{k-1}][x, z]\), \(h\) will be an element of this ring

  • k (Integer) – index of the parameter \(t_k\) which will be reconstructed

Returns:

h (PolyElement) – reconstructed polynomial in \(\mathbb Z(t_k)[t_1, \ldots, t_{k-1}][x, z]\) or None

diofant.polys.modulargcd._rational_reconstruction_int_coeffs(hm, m, ring)[source]

Reconstruct every rational coefficient \(c_h\) of a polynomial \(h\) in \(\mathbb Q[t_1, \ldots, t_k][x, z]\) from the corresponding integer coefficient \(c_{h_m}\) of a polynomial \(h_m\) in \(\mathbb Z[t_1, \ldots, t_k][x, z]\) such that

\[c_{h_m} = c_h \; \mathrm{mod} \, m,\]

where \(m \in \mathbb Z\).

The reconstruction is based on the Euclidean Algorithm. In general, \(m\) is not a prime number, so it is possible that this fails for some coefficient. In that case None is returned.

Parameters:
  • hm (PolyElement) – polynomial in \(\mathbb Z[t_1, \ldots, t_k][x, z]\)

  • m (Integer) – modulus, not necessarily prime

  • ring (PolynomialRing) – \(\mathbb Q[t_1, \ldots, t_k][x, z]\), \(h\) will be an element of this ring

Returns:

h (PolyElement) – reconstructed polynomial in \(\mathbb Q[t_1, \ldots, t_k][x, z]\) or None

diofant.polys.modulargcd._to_ANP_poly(f, ring)[source]

Convert a polynomial \(f \in \mathbb Z[x_1, \ldots, x_{n-1}][z]/(\check m_{\alpha}(z))[x_0]\) to a polynomial in \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\), where \(\check m_{\alpha}(z) \in \mathbb Z[z]\) is the primitive associate of the minimal polynomial \(m_{\alpha}(z)\) of \(\alpha\) over \(\mathbb Q\).

Parameters:
  • f (PolyElement) – polynomial in \(\mathbb Z[x_1, \ldots, x_{n-1}][x_0, z]\)

  • ring (PolynomialRing) – \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\)

Returns:

f_ (PolyElement) – polynomial in \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\)

diofant.polys.modulargcd._to_ZZ_poly(f, ring)[source]

Compute an associate of a polynomial \(f \in \mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\) in \(\mathbb Z[x_1, \ldots, x_{n-1}][z] / (\check m_{\alpha}(z))[x_0]\), where \(\check m_{\alpha}(z) \in \mathbb Z[z]\) is the primitive associate of the minimal polynomial \(m_{\alpha}(z)\) of \(\alpha\) over \(\mathbb Q\).

Parameters:
  • f (PolyElement) – polynomial in \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\)

  • ring (PolynomialRing) – \(\mathbb Z[x_1, \ldots, x_{n-1}][x_0, z]\)

Returns:

f_ (PolyElement) – associate of \(f\) in \(\mathbb Z[x_1, \ldots, x_{n-1}][x_0, z]\)

diofant.polys.modulargcd._trunc(f, minpoly, p)[source]

Compute the reduced representation of a polynomial \(f\) in \(\mathbb Z_p[z] / (\check m_{\alpha}(z))[x]\)

Parameters:
  • f (PolyElement) – polynomial in \(\mathbb Z[x, z]\)

  • minpoly (PolyElement) – polynomial \(\check m_{\alpha} \in \mathbb Z[z]\), not necessarily irreducible

  • p (Integer) – prime number, modulus of \(\mathbb Z_p\)

Returns:

ftrunc (PolyElement) – polynomial in \(\mathbb Z[x, z]\), reduced modulo \(\check m_{\alpha}(z)\) and \(p\)

diofant.polys.modulargcd.func_field_modgcd(f, g)[source]

Compute the GCD of two polynomials \(f\) and \(g\) in \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\) using a modular algorithm.

The algorithm first computes the primitive associate \(\check m_{\alpha}(z)\) of the minimal polynomial \(m_{\alpha}\) in \(\mathbb{Z}[z]\) and the primitive associates of \(f\) and \(g\) in \(\mathbb{Z}[x_1, \ldots, x_{n-1}][z]/(\check m_{\alpha})[x_0]\). Then it computes the GCD in \(\mathbb Q(x_1, \ldots, x_{n-1})[z]/(m_{\alpha}(z))[x_0]\). This is done by calculating the GCD in \(\mathbb{Z}_p(x_1, \ldots, x_{n-1})[z]/(\check m_{\alpha}(z))[x_0]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem and Rational Reconstuction. The GCD over \(\mathbb{Z}_p(x_1, \ldots, x_{n-1})[z]/(\check m_{\alpha}(z))[x_0]\) is computed with a recursive subroutine, which evaluates the polynomials at \(x_{n-1} = a\) for suitable evaluation points \(a \in \mathbb Z_p\) and then calls itself recursively until the ground domain does no longer contain any parameters. For \(\mathbb{Z}_p[z]/(\check m_{\alpha}(z))[x_0]\) the Euclidean Algorithm is used. The results of those recursive calls are then interpolated and Rational Function Reconstruction is used to obtain the correct coefficients. The results, both in \(\mathbb Q(x_1, \ldots, x_{n-1})[z]/(m_{\alpha}(z))[x_0]\) and \(\mathbb{Z}_p(x_1, \ldots, x_{n-1})[z]/(\check m_{\alpha}(z))[x_0]\), are verified by a fraction free trial division.

Apart from the above GCD computation some GCDs in \(\mathbb Q(\alpha)[x_1, \ldots, x_{n-1}]\) have to be calculated, because treating the polynomials as univariate ones can result in a spurious content of the GCD. For this func_field_modgcd is called recursively.

Parameters:

f, g (PolyElement) – polynomials in \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\)

Returns:

h (PolyElement) – monic GCD of the polynomials \(f\) and \(g\)

Examples

>>> A = QQ.algebraic_field(sqrt(2))
>>> _, x = ring('x', A)
>>> func_field_modgcd(x**2 - 2, x + sqrt(2))
x + sqrt(2)
>>> _, x, y = ring('x y', A)
>>> func_field_modgcd((x + sqrt(2)*y)**2, x + sqrt(2)*y)
x + sqrt(2)*y
>>> func_field_modgcd(x + sqrt(2)*y, x + y)
1

References

diofant.polys.modulargcd.modgcd(f, g)[source]

Compute the GCD of two polynomials in \(\mathbb{Z}[x_0, \ldots, x_{k-1}]\) using a modular algorithm.

The algorithm computes the GCD of two multivariate integer polynomials \(f\) and \(g\) by calculating the GCD in \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem. To compute the multivariate GCD over \(\mathbb{Z}_p\) the recursive subroutine _modgcd_p is used. To verify the result in \(\mathbb{Z}[x_0, \ldots, x_{k-1}]\), trial division is done, but only for candidates which are very likely the desired GCD.

Parameters:
  • f (PolyElement) – multivariate integer polynomial

  • g (PolyElement) – multivariate integer polynomial

Returns:

h (PolyElement) – GCD of the polynomials \(f\) and \(g\)

Examples

>>> _, x, y = ring('x y', ZZ)
>>> modgcd((x - y)*(x + y), (x + y)**2)
x + y
>>> _, x, y, z = ring('x y z', ZZ)
>>> modgcd((x - y)*z**2, (x**2 + 1)*z)
z

References

diofant.polys.modulargcd.trial_division(f, h, minpoly, p=None)[source]

Check if \(h\) divides \(f\) in \(\mathbb K[t_1, \ldots, t_k][z]/(m_{\alpha}(z))\), where \(\mathbb K\) is either \(\mathbb Q\) or \(\mathbb Z_p\).

This algorithm is based on pseudo division and does not use any fractions. By default \(\mathbb K\) is \(\mathbb Q\), if a prime number \(p\) is given, \(\mathbb Z_p\) is chosen instead.

Parameters:
  • f, h (PolyElement) – polynomials in \(\mathbb Z[t_1, \ldots, t_k][x, z]\)

  • minpoly (PolyElement) – polynomial \(m_{\alpha}(z)\) in \(\mathbb Z[t_1, \ldots, t_k][z]\)

  • p (Integer or None) – if \(p\) is given, \(\mathbb K\) is set to \(\mathbb Z_p\) instead of \(\mathbb Q\), default is None

Returns:

rem (PolyElement) – remainder of \(\frac f h\)

References

Heuristic GCD

_GCD._zz_heu_gcd(f, g)[source]

Heuristic polynomial GCD in Z[X].

Given univariate polynomials f and g in Z[X], returns their GCD, i.e. polynomial h:

h = gcd(f, g)

The algorithm is purely heuristic which means it may fail to compute the GCD. This will be signaled by raising an exception. In this case you will need to switch to another GCD method.

The algorithm computes the polynomial GCD by evaluating polynomials f and g at certain points and computing (fast) integer GCD of those evaluations. The polynomial GCD is recovered from the integer image by interpolation. The evaluation proces reduces f and g variable by variable into a large integer. The final step is to verify if the interpolated polynomial is the correct GCD.

References

Further tools

Real and complex root isolation and refinement algorithms.

class diofant.polys.rootisolation.ComplexInterval(a, b, I, Q, F1, F2, f1, f2, conj=False)[source]

A fully qualified representation of a complex isolation interval. The printed form is shown as (x1, y1) x (x2, y2): the southwest x northeast coordinates of the interval’s rectangle.

as_tuple()[source]

Return tuple representation of complex isolating interval.

property ax

Return x coordinate of south-western corner.

property ay

Return y coordinate of south-western corner.

property bx

Return x coordinate of north-eastern corner.

property by

Return y coordinate of north-eastern corner.

property center

Return the center of the complex isolating interval.

conjugate()[source]

Return conjugated isolating interval.

is_disjoint(other, check_re_refinement=False, re_disjoint=False)[source]

Return True if two isolation intervals are disjoint.

Parameters:
  • check_re_refinement (bool, optional) – If enabled, test that either real projections of isolation intervals are disjoint or roots share common real part.

  • re_disjoint (bool, optional) – If enabled, return True only if real projections of isolation intervals are disjoint.

refine(vertical=False)[source]

Perform one step of complex root refinement algorithm.

class diofant.polys.rootisolation.RealInterval(data, f)[source]

A fully qualified representation of a real isolation interval.

property a

Return the position of the left end.

as_tuple()[source]

Return tuple representation of real isolating interval.

property b

Return the position of the right end.

property center

Return the center of the real isolating interval.

is_disjoint(other)[source]

Return True if two isolation intervals are disjoint.

refine()[source]

Perform one step of real root refinement algorithm.

Square-free decomposition algorithms and related tools.

Undocumented

Many parts of the polys module are still undocumented, and even where there is documentation it is scarce. Please contribute!

Options manager for Poly and public API functions.

class diofant.polys.polyoptions.Order[source]

order option to polynomial manipulation functions.

Definitions of common exceptions for polys module.

exception diofant.polys.polyerrors.BasePolynomialError[source]

Base class for polynomial related exceptions.

exception diofant.polys.polyerrors.CoercionFailedError[source]

Raised when a coercion is failed.

exception diofant.polys.polyerrors.ComputationFailedError(func, nargs, exc)[source]

Raised when polynomial computation failed.

exception diofant.polys.polyerrors.DomainError[source]

Generic domain error.

exception diofant.polys.polyerrors.EvaluationFailedError[source]

Raised when a polynomial evaluation is failed.

exception diofant.polys.polyerrors.ExactQuotientFailedError(f, g, dom=None)[source]

Raised when exact quotient is failed.

exception diofant.polys.polyerrors.ExtraneousFactorsError[source]

Raised when there are extraneous factors.

exception diofant.polys.polyerrors.FlagError[source]

Generic flag error.

exception diofant.polys.polyerrors.GeneratorsError[source]

Raised when polynomial generators are unsuitable.

exception diofant.polys.polyerrors.GeneratorsNeededError[source]

Raised when more generators needed.

exception diofant.polys.polyerrors.HeuristicGCDFailedError[source]

Raised when a heuristic GCD is failed.

exception diofant.polys.polyerrors.HomomorphismFailedError[source]

Raised when a homomorphism is failed.

exception diofant.polys.polyerrors.IsomorphismFailedError[source]

Raised when an isomprphism is failed.

exception diofant.polys.polyerrors.ModularGCDFailedError[source]

Raised when a modular GCD is failed.

exception diofant.polys.polyerrors.MultivariatePolynomialError[source]

Generic multivariate polynomial error.

exception diofant.polys.polyerrors.NotAlgebraicError[source]

Raised when a non algebraic element occurred.

exception diofant.polys.polyerrors.NotInvertibleError[source]

Raised when a element is not invertible.

exception diofant.polys.polyerrors.NotReversibleError[source]

Raised when a element is not reversible.

exception diofant.polys.polyerrors.OperationNotSupportedError(poly, func)[source]

Raised when an operation is not supported.

exception diofant.polys.polyerrors.OptionError[source]

Generic option error.

exception diofant.polys.polyerrors.PolificationFailedError(opt, origs, exprs, seq=False)[source]

Raised if polunomial construction is failed.

exception diofant.polys.polyerrors.PolynomialDivisionFailedError(f, g, domain)[source]

Raised when polynomial division is failed.

exception diofant.polys.polyerrors.PolynomialError[source]

Generic polynomial error.

exception diofant.polys.polyerrors.RefinementFailedError[source]

Raised when a root refinement is failed.

exception diofant.polys.polyerrors.UnificationFailedError[source]

Raised when domains unification failed.

exception diofant.polys.polyerrors.UnivariatePolynomialError[source]

Generic univariate polynomial error.

exception diofant.polys.polyerrors.UnluckyLeadingCoefficientError[source]

Raised when there are unlucky LC.

class diofant.polys.fields.FracElement(numer, denom=None)[source]

Element of multivariate distributed rational function field.

See also

FractionField

compose(x, a=None)[source]

Computes the functional composition.

diff(x)[source]

Computes partial derivative in x.

Examples

>>> _, x, y, z = field('x y z', ZZ)
>>> ((x**2 + y)/(z + 1)).diff(x)
2*x/(z + 1)