Internals of the Polynomial Manipulation Module

The implementation of the polynomials module is structured internally in “levels”. There are four levels, called L0, L1, L2 and L3. The levels three and four contain the user-facing functionality and were described in the previous section. This section focuses on levels zero and one.

Level zero provides core polynomial manipulation functionality with C-like, low-level interfaces. Level one wraps this low-level functionality into object oriented structures. These are not the classes seen by the user, but rather classes used internally throughout the polys module.

There is one additional complication in the implementation. This comes from the fact that 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)).

Note that there is some amount of circularity: the polynomial ring domains use the level one classes, the level one classes use the level zero functions, and level zero functions use domains. It is possible, in principle, but not in the current implementation, to work in rings like \(k[X][Y]\). This would create even more layers. For this reason, working in the isomorphic ring \(k[X, Y]\) is preferred.

Level One

class diofant.polys.polyclasses.DMP(rep, dom, lev=None)[source]

Dense Multivariate Polynomials over \(K\).

LC()[source]

Returns the leading coefficient of self.

TC()[source]

Returns the trailing coefficient of self.

abs()[source]

Make all coefficients in self positive.

add(other)[source]

Add two multivariate polynomials self and other.

add_ground(c)[source]

Add an element of the ground domain to self.

all_coeffs()[source]

Returns all coefficients from self.

all_monoms()[source]

Returns all monomials from self.

all_terms()[source]

Returns all terms from a self.

cancel(other, include=True)[source]

Cancel common factors in a rational function self/other.

clear_denoms()[source]

Clear denominators, but keep the ground domain.

coeffs(order=None)[source]

Returns all non-zero coefficients from self in lex order.

cofactors(other)[source]

Returns GCD of self and other and their cofactors.

compose(other)[source]

Computes functional composition of self and other.

content()[source]

Returns GCD of polynomial coefficients.

convert(dom)[source]

Convert the ground domain of self.

count_complex_roots(inf=None, sup=None)[source]

Return the number of complex roots of self in [inf, sup].

count_real_roots(inf=None, sup=None)[source]

Return the number of real roots of self in [inf, sup].

decompose()[source]

Computes functional decomposition of self.

deflate()[source]

Reduce degree of \(self\) by mapping \(x_i^m\) to \(y_i\).

degree(j=0)[source]

Returns the leading degree of self in x_j.

degree_list()[source]

Returns a list of degrees of self.

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

Computes the m-th order derivative of self in x_j.

discriminant()[source]

Computes discriminant of self.

div(other)[source]

Polynomial division with remainder of self and other.

eject(dom, front=False)[source]

Eject selected generators into the ground domain.

eval(a, j=0)[source]

Evaluates self at the given point a in x_j.

exclude()[source]

Remove useless generators from self.

Returns the removed generators and the new excluded self.

Examples

>>> from diofant.domains import ZZ
>>> DMP([[[ZZ(1)]], [[ZZ(1)], [ZZ(2)]]], ZZ).exclude()
([2], DMP([[1], [1, 2]], ZZ))
exquo(other)[source]

Computes polynomial exact quotient of self and other.

exquo_ground(c)[source]

Exact quotient of self by a an element of the ground domain.

factor_list()[source]

Returns a list of irreducible factors of self.

factor_list_include()[source]

Returns a list of irreducible factors of self.

classmethod from_dict(rep, lev, dom)[source]

Construct and instance of cls from a dict representation.

classmethod from_diofant_list(rep, lev, dom)[source]

Create an instance of cls given a list of Diofant coefficients.

classmethod from_list(rep, lev, dom)[source]

Create an instance of cls given a list of native coefficients.

gcd(other)[source]

Returns polynomial GCD of self and other.

gcdex(other)[source]

Extended Euclidean algorithm, if univariate.

gff_list()[source]

Computes greatest factorial factorization of self.

half_gcdex(other)[source]

Half extended Euclidean algorithm, if univariate.

homogeneous_order()[source]

Returns the homogeneous order of self.

homogenize(s)[source]

Return homogeneous polynomial of self

inject(front=False)[source]

Inject ground domain generators into self.

integrate(m=1, j=0)[source]

Computes the m-th order indefinite integral of self in x_j.

intervals(all=False, eps=None, inf=None, sup=None, fast=False, sqf=False)[source]

Compute isolating intervals for roots of self.

invert(other)[source]

Invert self modulo other, if possible.

is_cyclotomic

Returns True if self is a cyclotomic polynomial.

is_ground

Returns True if self is an element of the ground domain.

is_homogeneous

Returns True if self is a homogeneous polynomial.

is_irreducible

Returns True if self has no factors over its domain.

is_linear

Returns True if self is linear in all its variables.

is_monic

Returns True if the leading coefficient of self is one.

is_monomial

Returns True if self is zero or has only one term.

is_one

Returns True if self is a unit polynomial.

is_primitive

Returns True if the GCD of the coefficients of self is one.

is_quadratic

Returns True if self is quadratic in all its variables.

is_sqf

Returns True if self is a square-free polynomial.

is_zero

Returns True if self is a zero polynomial.

l1_norm()[source]

Returns l1 norm of self.

lcm(other)[source]

Returns polynomial LCM of self and other.

lift()[source]

Convert algebraic coefficients to rationals.

max_norm()[source]

Returns maximum norm of self.

monic()[source]

Divides all coefficients by LC(self).

monoms(order=None)[source]

Returns all non-zero monomials from self in lex order.

mul(other)[source]

Multiply two multivariate polynomials f and g.

mul_ground(c)[source]

Multiply self by a an element of the ground domain.

neg()[source]

Negate all coefficients in self.

nth(*N)[source]

Returns the n-th coefficient of self.

pdiv(other)[source]

Polynomial pseudo-division of self and other.

per(rep, dom=None, kill=False)[source]

Create a DMP out of the given representation.

permute(P)[source]

Returns a polynomial in \(K[x_{P(1)}, ..., x_{P(n)}]\).

Examples

>>> from diofant.domains import ZZ
>>> DMP([[[ZZ(2)], [ZZ(1), ZZ(0)]], [[]]], ZZ).permute([1, 0, 2])
DMP([[[2], []], [[1, 0], []]], ZZ)
>>> DMP([[[ZZ(2)], [ZZ(1), ZZ(0)]], [[]]], ZZ).permute([1, 2, 0])
DMP([[[1], []], [[2, 0], []]], ZZ)
pexquo(other)[source]

Polynomial exact pseudo-quotient of self and other.

pow(n)[source]

Raise self to a non-negative power n.

pquo(other)[source]

Polynomial pseudo-quotient of self and other.

prem(other)[source]

Polynomial pseudo-remainder of self and other.

primitive()[source]

Returns content and a primitive form of self.

quo(other)[source]

Computes polynomial quotient of self and other.

quo_ground(c)[source]

Quotient of self by a an element of the ground domain.

refine_root(s, t, eps=None, steps=None, fast=False)[source]

Refine an isolating interval to the given precision.

eps should be a rational number.

rem(other)[source]

Computes polynomial remainder of self and other.

resultant(other, includePRS=False)[source]

Computes resultant of self and other via PRS.

revert(n)[source]

Compute self**(-1) mod x**n.

shift(a)[source]

Efficiently compute Taylor shift self(x + a).

slice(m, n, j=0)[source]

Take a continuous subsequence of terms of self.

sqf_list(all=False)[source]

Returns a list of square-free factors of self.

sqf_list_include(all=False)[source]

Returns a list of square-free factors of self.

sqf_norm()[source]

Computes square-free norm of self.

sqf_part()[source]

Computes square-free part of self.

sqr()[source]

Square a multivariate polynomial self.

sturm()[source]

Computes the Sturm sequence of self.

sub(other)[source]

Subtract two multivariate polynomials self and other.

sub_ground(c)[source]

Subtract an element of the ground domain from self.

subresultants(other)[source]

Computes subresultant PRS sequence of self and other.

terms(order=None)[source]

Returns all non-zero terms from self in lex order.

terms_gcd()[source]

Remove GCD of terms from the polynomial self.

to_dict(zero=False)[source]

Convert self to a dict representation with native coefficients.

to_diofant_dict(zero=False)[source]

Convert self to a dict representation with Diofant coefficients.

to_exact()[source]

Make the ground domain exact.

to_field()[source]

Make the ground domain a field.

to_ring()[source]

Make the ground domain a ring.

to_tuple()[source]

Convert self to a tuple representation with native coefficients.

This is needed for hashing.

total_degree()[source]

Returns the total degree of self.

trunc(p)[source]

Reduce self modulo a constant p.

unify(other)[source]

Unify representations of two multivariate polynomials.

class diofant.polys.polyclasses.DMF(rep, dom, lev=None)[source]

Dense Multivariate Fractions over \(K\).

add(other)[source]

Add two multivariate fractions self and other.

denom()[source]

Returns the denominator of self.

exquo(other)

Computes quotient of fractions self and other.

frac_unify(other)[source]

Unify representations of two multivariate fractions.

half_per(rep, kill=False)[source]

Create a DMP out of the given representation.

invert(check=True)[source]

Computes inverse of a fraction self.

is_one

Returns True if self is a unit fraction.

is_zero

Returns True if self is a zero fraction.

mul(other)[source]

Multiply two multivariate fractions self and other.

neg()[source]

Negate all coefficients in self.

numer()[source]

Returns the numerator of self.

per(num, den, cancel=True, kill=False)[source]

Create a DMF out of the given representation.

poly_unify(other)[source]

Unify a multivariate fraction and a polynomial.

pow(n)[source]

Raise self to a non-negative power n.

quo(other)[source]

Computes quotient of fractions self and other.

sub(other)[source]

Subtract two multivariate fractions self and other.

class diofant.polys.polyclasses.ANP(rep, mod, dom)[source]

Dense Algebraic Number Polynomials over a field.

LC()[source]

Returns the leading coefficient of self.

TC()[source]

Returns the trailing coefficient of self.

is_ground

Returns True if self is an element of the ground domain.

is_one

Returns True if self is a unit algebraic number.

is_zero

Returns True if self is a zero algebraic number.

pow(n)[source]

Raise self to an integer power n.

to_dict()[source]

Convert self to a dict representation with native coefficients.

to_diofant_dict()[source]

Convert self to a dict representation with Diofant coefficients.

to_diofant_list()[source]

Convert self to a list representation with Diofant coefficients.

to_list()[source]

Convert self to a list representation with native coefficients.

to_tuple()[source]

Convert self to a tuple representation with native coefficients.

This is needed for hashing.

unify(other)[source]

Unify representations of two algebraic numbers.

Level Zero

Level zero contains the bulk code of the polynomial manipulation module.

Manipulation of dense, multivariate polynomials

These functions can be used to manipulate polynomials in \(K[X_0, \ldots, X_u]\). Functions for manipulating multivariate polynomials in the dense representation have the prefix dmp_. Functions which only apply to univariate polynomials (i.e. \(u = 0\)) have the prefix dup__. The ground domain \(K\) has to be passed explicitly. For many multivariate polynomial manipulation functions also the level \(u\), i.e. the number of generators minus one, has to be passed. (Note that, in many cases, dup_ versions of functions are available, which may be slightly more efficient.)

Basic manipulation:

diofant.polys.densebasic.dmp_LC(f, K)

Return leading coefficient of f.

Examples

>>> from diofant.domains import ZZ
>>> poly_LC([], ZZ)
0
>>> poly_LC([ZZ(1), ZZ(2), ZZ(3)], ZZ)
1
diofant.polys.densebasic.dmp_TC(f, K)

Return trailing coefficient of f.

Examples

>>> from diofant.domains import ZZ
>>> poly_TC([], ZZ)
0
>>> poly_TC([ZZ(1), ZZ(2), ZZ(3)], ZZ)
3
diofant.polys.densebasic.dmp_ground_LC(f, u, K)[source]

Return the ground leading coefficient.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[[1], [2, 3]]])
>>> dmp_ground_LC(f, 2, ZZ)
1
diofant.polys.densebasic.dmp_ground_TC(f, u, K)[source]

Return the ground trailing coefficient.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[[1], [2, 3]]])
>>> dmp_ground_TC(f, 2, ZZ)
3
diofant.polys.densebasic.dmp_true_LT(f, u, K)[source]

Return the leading term c * x_1**n_1 ... x_k**n_k.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[4], [2, 0], [3, 0, 0]])
>>> dmp_true_LT(f, 1, ZZ)
((2, 0), 4)
diofant.polys.densebasic.dmp_degree(f, u)[source]

Return the leading degree of f in x_0 in K[X].

Note that the degree of 0 is negative infinity (the Diofant object -oo).

Examples

>>> from diofant.domains import ZZ
>>> dmp_degree([[[]]], 2)
-oo
>>> f = ZZ.map([[2], [1, 2, 3]])
>>> dmp_degree(f, 1)
1
diofant.polys.densebasic.dmp_degree_in(f, j, u)[source]

Return the leading degree of f in x_j in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[2], [1, 2, 3]])
>>> dmp_degree_in(f, 0, 1)
1
>>> dmp_degree_in(f, 1, 1)
2
diofant.polys.densebasic.dmp_degree_list(f, u)[source]

Return a list of degrees of f in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1], [1, 2, 3]])
>>> dmp_degree_list(f, 1)
(1, 2)
diofant.polys.densebasic.dmp_strip(f, u)[source]

Remove leading zeros from f in K[X].

Examples

>>> dmp_strip([[], [0, 1, 2], [1]], 1)
[[0, 1, 2], [1]]
diofant.polys.densebasic.dmp_validate(f, K=None)[source]

Return the number of levels in f and recursively strip it.

Examples

>>> dmp_validate([[], [0, 1, 2], [1]])
([[1, 2], [1]], 1)
>>> dmp_validate([[1], 1])
Traceback (most recent call last):
...
ValueError: invalid data structure for a multivariate polynomial
diofant.polys.densebasic.dup_reverse(f)[source]

Compute x**n * f(1/x), i.e.: reverse f in K[x].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([1, 2, 3, 0])
>>> dup_reverse(f)
[3, 2, 1]
diofant.polys.densebasic.dmp_copy(f, u)[source]

Create a new copy of a polynomial f in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1], [1, 2]])
>>> dmp_copy(f, 1)
[[1], [1, 2]]
diofant.polys.densebasic.dmp_to_tuple(f, u)[source]

Convert \(f\) into a nested tuple of tuples.

This is needed for hashing. This is similar to dmp_copy().

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1], [1, 2]])
>>> dmp_to_tuple(f, 1)
((1,), (1, 2))
diofant.polys.densebasic.dmp_normal(f, u, K)[source]

Normalize a multivariate polynomial in the given domain.

Examples

>>> from diofant.domains import ZZ
>>> dmp_normal([[], [0, 1.5, 2]], 1, ZZ)
[[1, 2]]
diofant.polys.densebasic.dmp_convert(f, u, K0, K1)[source]

Convert the ground domain of f from K0 to K1.

Examples

>>> from diofant.polys.rings import ring
>>> from diofant.domains import ZZ
>>> R, x = ring("x", ZZ)
>>> dmp_convert([[R(1)], [R(2)]], 1, R.to_domain(), ZZ)
[[1], [2]]
>>> dmp_convert([[ZZ(1)], [ZZ(2)]], 1, ZZ, R.to_domain())
[[1], [2]]
diofant.polys.densebasic.dmp_from_diofant(f, u, K)[source]

Convert the ground domain of f from Diofant to K.

Examples

>>> from diofant import Integer
>>> from diofant.domains import ZZ
>>> dmp_from_diofant([[Integer(1)], [Integer(2)]], 1, ZZ)
[[1], [2]]
diofant.polys.densebasic.dmp_nth(f, n, u, K)[source]

Return the n-th coefficient of f in K[x].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1], [2], [3]])
>>> dmp_nth(f, 0, 1, ZZ)
[3]
>>> dmp_nth(f, 4, 1, ZZ)
[]
diofant.polys.densebasic.dmp_ground_nth(f, N, u, K)[source]

Return the ground n-th coefficient of f in K[x].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1], [2, 3]])
>>> dmp_ground_nth(f, (0, 1), 1, ZZ)
2
diofant.polys.densebasic.dmp_zero_p(f, u)[source]

Return True if f is zero in K[X].

Examples

>>> dmp_zero_p([[[[[]]]]], 4)
True
>>> dmp_zero_p([[[[[1]]]]], 4)
False
diofant.polys.densebasic.dmp_zero(u)[source]

Return a multivariate zero.

Examples

>>> dmp_zero(4)
[[[[[]]]]]
diofant.polys.densebasic.dmp_one_p(f, u, K)[source]

Return True if f is one in K[X].

Examples

>>> from diofant.domains import ZZ
>>> dmp_one_p([[[ZZ(1)]]], 2, ZZ)
True
diofant.polys.densebasic.dmp_one(u, K)[source]

Return a multivariate one over K.

Examples

>>> from diofant.domains import ZZ
>>> dmp_one(2, ZZ)
[[[1]]]
diofant.polys.densebasic.dmp_ground_p(f, c, u)[source]

Return True if f is constant in K[X].

Examples

>>> dmp_ground_p([[[3]]], 3, 2)
True
>>> dmp_ground_p([[[4]]], None, 2)
True
diofant.polys.densebasic.dmp_ground(c, u)[source]

Return a multivariate constant.

Examples

>>> dmp_ground(3, 5)
[[[[[[3]]]]]]
>>> dmp_ground(1, -1)
1
diofant.polys.densebasic.dmp_zeros(n, u, K)[source]

Return a list of multivariate zeros.

Examples

>>> from diofant.domains import ZZ
>>> dmp_zeros(3, 2, ZZ)
[[[[]]], [[[]]], [[[]]]]
>>> dmp_zeros(3, -1, ZZ)
[0, 0, 0]
diofant.polys.densebasic.dmp_grounds(c, n, u)[source]

Return a list of multivariate constants.

Examples

>>> from diofant.domains import ZZ
>>> dmp_grounds(ZZ(4), 3, 2)
[[[[4]]], [[[4]]], [[[4]]]]
>>> dmp_grounds(ZZ(4), 3, -1)
[4, 4, 4]
diofant.polys.densebasic.dmp_negative_p(f, u, K)[source]

Return True if LC(f) is negative.

Examples

>>> from diofant.domains import ZZ
>>> dmp_negative_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
False
>>> dmp_negative_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
True
diofant.polys.densebasic.dmp_positive_p(f, u, K)[source]

Return True if LC(f) is positive.

Examples

>>> from diofant.domains import ZZ
>>> dmp_positive_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
True
>>> dmp_positive_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
False
diofant.polys.densebasic.dmp_from_dict(f, u, K)[source]

Create a K[X] polynomial from a dict.

Examples

>>> from diofant.domains import ZZ
>>> dmp_from_dict({(0, 0): ZZ(3), (0, 1): ZZ(2), (2, 1): ZZ(1)}, 1, ZZ)
[[1, 0], [], [2, 3]]
>>> dmp_from_dict({}, 0, ZZ)
[]
diofant.polys.densebasic.dmp_to_dict(f, u, K=None, zero=False)[source]

Convert a K[X] polynomial to a dict``.

Examples

>>> dmp_to_dict([[1, 0], [], [2, 3]], 1)
{(0, 0): 3, (0, 1): 2, (2, 1): 1}
>>> dmp_to_dict([], 0)
{}
diofant.polys.densebasic.dmp_swap(f, i, j, u, K)[source]

Transform K[..x_i..x_j..] to K[..x_j..x_i..].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[[2], [1, 0]], []])
>>> dmp_swap(f, 0, 1, 2, ZZ)
[[[2], []], [[1, 0], []]]
>>> dmp_swap(f, 1, 2, 2, ZZ)
[[[1], [2, 0]], [[]]]
>>> dmp_swap(f, 0, 2, 2, ZZ)
[[[1, 0]], [[2, 0], []]]
diofant.polys.densebasic.dmp_permute(f, P, u, K)[source]

Return a polynomial in K[x_{P(1)},..,x_{P(n)}].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[[2], [1, 0]], []])
>>> dmp_permute(f, [1, 0, 2], 2, ZZ)
[[[2], []], [[1, 0], []]]
>>> dmp_permute(f, [1, 2, 0], 2, ZZ)
[[[1], []], [[2, 0], []]]
diofant.polys.densebasic.dmp_nest(f, l, K)[source]

Return a multivariate value nested l-levels.

Examples

>>> from diofant.domains import ZZ
>>> dmp_nest([[ZZ(1)]], 2, ZZ)
[[[[1]]]]
diofant.polys.densebasic.dmp_raise(f, l, u, K)[source]

Return a multivariate polynomial raised l-levels.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[], [1, 2]])
>>> dmp_raise(f, 2, 1, ZZ)
[[[[]]], [[[1]], [[2]]]]
diofant.polys.densebasic.dmp_deflate(f, u, K)[source]

Map x_i**m_i to y_i in a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
>>> dmp_deflate(f, 1, ZZ)
((2, 3), [[1, 2], [3, 4]])
diofant.polys.densebasic.dmp_multi_deflate(polys, u, K)[source]

Map x_i**m_i to y_i in a set of polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
>>> g = ZZ.map([[1, 0, 2], [], [3, 0, 4]])
>>> dmp_multi_deflate((f, g), 1, ZZ)
((2, 1), ([[1, 0, 0, 2], [3, 0, 0, 4]], [[1, 0, 2], [3, 0, 4]]))
diofant.polys.densebasic.dmp_inflate(f, M, u, K)[source]

Map y_i to x_i**k_i in a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1, 2], [3, 4]])
>>> dmp_inflate(f, (2, 3), 1, ZZ)
[[1, 0, 0, 2], [], [3, 0, 0, 4]]
diofant.polys.densebasic.dmp_exclude(f, u, K)[source]

Exclude useless levels from f.

Return the levels excluded, the new excluded f, and the new u.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[[1]], [[1], [2]]])
>>> dmp_exclude(f, 2, ZZ)
([2], [[1], [1, 2]], 1)
diofant.polys.densebasic.dmp_include(f, J, u, K)[source]

Include useless levels in f.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1], [1, 2]])
>>> dmp_include(f, [2], 1, ZZ)
[[[1]], [[1], [2]]]
diofant.polys.densebasic.dmp_inject(f, u, K, front=False)[source]

Convert f from K[X][Y] to K[X,Y].

Examples

>>> from diofant.polys.rings import ring
>>> from diofant.domains import ZZ
>>> R, x, y = ring("x y", ZZ)
>>> dmp_inject([R(1), x + 2], 0, R.to_domain())
([[[1]], [[1], [2]]], 2)
>>> dmp_inject([R(1), x + 2], 0, R.to_domain(), front=True)
([[[1]], [[1, 2]]], 2)
diofant.polys.densebasic.dmp_eject(f, u, K, front=False)[source]

Convert f from K[X,Y] to K[X][Y].

Examples

>>> from diofant.domains import ZZ
>>> dmp_eject([[[1]], [[1], [2]]], 2, ZZ['x', 'y'])
[1, x + 2]
diofant.polys.densebasic.dmp_terms_gcd(f, u, K)[source]

Remove GCD of terms from f in K[X].

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1, 0], [1, 0, 0], [], []])
>>> dmp_terms_gcd(f, 1, ZZ)
((2, 1), [[1], [1, 0]])
diofant.polys.densebasic.dmp_list_terms(f, u, K, order=None)[source]

List all non-zero terms from f in the given order order.

Examples

>>> from diofant.domains import ZZ
>>> f = ZZ.map([[1, 1], [2, 3]])
>>> dmp_list_terms(f, 1, ZZ)
[((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]
>>> dmp_list_terms(f, 1, ZZ, order='grevlex')
[((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]
diofant.polys.densebasic.dmp_apply_pairs(f, g, h, args, u, K)[source]

Apply h to pairs of coefficients of f and g.

Examples

>>> from diofant.domains import ZZ
>>> h = lambda x, y, z: 2*x + y - z
>>> dmp_apply_pairs([[1], [2, 3]], [[3], [2, 1]], h, [1], 1, ZZ)
[[4], [5, 6]]
diofant.polys.densebasic.dmp_slice(f, m, n, u, K)[source]

Take a continuous subsequence of terms of f in K[X].

diofant.polys.densebasic.dup_random(n, a, b, K)[source]

Return a polynomial of degree n with coefficients in [a, b].

Examples

>>> from diofant.domains import ZZ
>>> dup_random(3, -10, 10, ZZ) 
[-2, -8, 9, -4]

Arithmetic operations:

diofant.polys.densearith.dmp_add_term(f, c, i, u, K)[source]

Add c(x_2..x_u)*x_0**i to f in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_add_term(x*y + 1, 2, 2)
2*x**2 + x*y + 1
diofant.polys.densearith.dmp_sub_term(f, c, i, u, K)[source]

Subtract c(x_2..x_u)*x_0**i from f in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_sub_term(2*x**2 + x*y + 1, 2, 2)
x*y + 1
diofant.polys.densearith.dmp_mul_term(f, c, i, u, K)[source]

Multiply f by c(x_2..x_u)*x_0**i in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_mul_term(x**2*y + x, 3*y, 2)
3*x**4*y**2 + 3*x**3*y
diofant.polys.densearith.dmp_add_ground(f, c, u, K)[source]

Add an element of the ground domain to f.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_add_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))
x**3 + 2*x**2 + 3*x + 8
diofant.polys.densearith.dmp_sub_ground(f, c, u, K)[source]

Subtract an element of the ground domain from f.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_sub_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))
x**3 + 2*x**2 + 3*x
diofant.polys.densearith.dmp_mul_ground(f, c, u, K)[source]

Multiply f by a constant value in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_mul_ground(2*x + 2*y, ZZ(3))
6*x + 6*y
diofant.polys.densearith.dmp_quo_ground(f, c, u, K)[source]

Quotient by a constant in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_quo_ground(2*x**2*y + 3*x, ZZ(2))
x**2*y + x
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_quo_ground(2*x**2*y + 3*x, QQ(2))
x**2*y + 3/2*x
diofant.polys.densearith.dmp_exquo_ground(f, c, u, K)[source]

Exact quotient by a constant in K[X].

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_exquo_ground(x**2*y + 2*x, QQ(2))
1/2*x**2*y + x
diofant.polys.densearith.dup_lshift(f, n, K)[source]

Efficiently multiply f by x**n in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_lshift(x**2 + 1, 2)
x**4 + x**2
diofant.polys.densearith.dup_rshift(f, n, K)[source]

Efficiently divide f by x**n in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_rshift(x**4 + x**2, 2)
x**2 + 1
>>> R.dup_rshift(x**4 + x**2 + 2, 2)
x**2 + 1
diofant.polys.densearith.dmp_abs(f, u, K)[source]

Make all coefficients positive in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_abs(x**2*y - x)
x**2*y + x
diofant.polys.densearith.dmp_neg(f, u, K)[source]

Negate a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_neg(x**2*y - x)
-x**2*y + x
diofant.polys.densearith.dmp_add(f, g, u, K)[source]

Add dense polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_add(x**2 + y, x**2*y + x)
x**2*y + x**2 + x + y
diofant.polys.densearith.dmp_sub(f, g, u, K)[source]

Subtract dense polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_sub(x**2 + y, x**2*y + x)
-x**2*y + x**2 - x + y
diofant.polys.densearith.dmp_add_mul(f, g, h, u, K)[source]

Returns f + g*h where f, g, h are in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_add_mul(x**2 + y, x, x + 2)
2*x**2 + 2*x + y
diofant.polys.densearith.dmp_sub_mul(f, g, h, u, K)[source]

Returns f - g*h where f, g, h are in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_sub_mul(x**2 + y, x, x + 2)
-2*x + y
diofant.polys.densearith.dmp_mul(f, g, u, K)[source]

Multiply dense polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_mul(x*y + 1, x)
x**2*y + x
diofant.polys.densearith.dmp_sqr(f, u, K)[source]

Square dense polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_sqr(x**2 + x*y + y**2)
x**4 + 2*x**3*y + 3*x**2*y**2 + 2*x*y**3 + y**4
diofant.polys.densearith.dmp_pow(f, n, u, K)[source]

Raise f to the n-th power in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_pow(x*y + 1, 3)
x**3*y**3 + 3*x**2*y**2 + 3*x*y + 1
diofant.polys.densearith.dmp_pdiv(f, g, u, K)[source]

Polynomial pseudo-division in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_pdiv(x**2 + x*y, 2*x + 2)
(2*x + 2*y - 2, -4*y + 4)
diofant.polys.densearith.dmp_prem(f, g, u, K)[source]

Polynomial pseudo-remainder in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_prem(x**2 + x*y, 2*x + 2)
-4*y + 4
diofant.polys.densearith.dmp_pquo(f, g, u, K)[source]

Polynomial exact pseudo-quotient in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + x*y
>>> g = 2*x + 2*y
>>> h = 2*x + 2
>>> R.dmp_pquo(f, g)
2*x
>>> R.dmp_pquo(f, h)
2*x + 2*y - 2
diofant.polys.densearith.dmp_pexquo(f, g, u, K)[source]

Polynomial pseudo-quotient in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + x*y
>>> g = 2*x + 2*y
>>> h = 2*x + 2
>>> R.dmp_pexquo(f, g)
2*x
>>> R.dmp_pexquo(f, h)
Traceback (most recent call last):
...
ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]
diofant.polys.densearith.dmp_rr_div(f, g, u, K)[source]

Multivariate division with remainder over a ring.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_rr_div(x**2 + x*y, 2*x + 2)
(0, x**2 + x*y)
diofant.polys.densearith.dmp_ff_div(f, g, u, K)[source]

Polynomial division with remainder over a field.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_ff_div(x**2 + x*y, 2*x + 2)
(1/2*x + 1/2*y - 1/2, -y + 1)
diofant.polys.densearith.dmp_div(f, g, u, K)[source]

Polynomial division with remainder in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_div(x**2 + x*y, 2*x + 2)
(0, x**2 + x*y)
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_div(x**2 + x*y, 2*x + 2)
(1/2*x + 1/2*y - 1/2, -y + 1)
diofant.polys.densearith.dmp_rem(f, g, u, K)[source]

Returns polynomial remainder in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_rem(x**2 + x*y, 2*x + 2)
x**2 + x*y
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_rem(x**2 + x*y, 2*x + 2)
-y + 1
diofant.polys.densearith.dmp_quo(f, g, u, K)[source]

Returns exact polynomial quotient in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_quo(x**2 + x*y, 2*x + 2)
0
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_quo(x**2 + x*y, 2*x + 2)
1/2*x + 1/2*y - 1/2
diofant.polys.densearith.dmp_exquo(f, g, u, K)[source]

Returns polynomial quotient in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + x*y
>>> g = x + y
>>> h = 2*x + 2
>>> R.dmp_exquo(f, g)
x
>>> R.dmp_exquo(f, h)
Traceback (most recent call last):
...
ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]
diofant.polys.densearith.dmp_max_norm(f, u, K)[source]

Returns maximum norm of a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_max_norm(2*x*y - x - 3)
3
diofant.polys.densearith.dmp_l1_norm(f, u, K)[source]

Returns l1 norm of a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_l1_norm(2*x*y - x - 3)
6
diofant.polys.densearith.dmp_expand(polys, u, K)[source]

Multiply together several polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_expand([x**2 + y**2, x + 1])
x**3 + x**2 + x*y**2 + y**2

Further tools:

diofant.polys.densetools.dmp_integrate(f, m, u, K)[source]

Computes the indefinite integral of f in x_0 in K[X].

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_integrate(x + 2*y, 1)
1/2*x**2 + 2*x*y
>>> R.dmp_integrate(x + 2*y, 2)
1/6*x**3 + x**2*y
diofant.polys.densetools.dmp_integrate_in(f, m, j, u, K)[source]

Computes the indefinite integral of f in x_j in K[X].

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> R.dmp_integrate_in(x + 2*y, 1, 0)
1/2*x**2 + 2*x*y
>>> R.dmp_integrate_in(x + 2*y, 1, 1)
x*y + y**2
diofant.polys.densetools.dmp_diff(f, m, u, K)[source]

m-th order derivative in x_0 of a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1
>>> R.dmp_diff(f, 1)
y**2 + 2*y + 3
>>> R.dmp_diff(f, 2)
0
diofant.polys.densetools.dmp_diff_in(f, m, j, u, K)[source]

m-th order derivative in x_j of a polynomial in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1
>>> R.dmp_diff_in(f, 1, 0)
y**2 + 2*y + 3
>>> R.dmp_diff_in(f, 1, 1)
2*x*y + 2*x + 4*y + 3
diofant.polys.densetools.dmp_eval(f, a, u, K)[source]

Evaluate a polynomial at x_0 = a in K[X] using the Horner scheme.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_eval(2*x*y + 3*x + y + 2, 2)
5*y + 8
diofant.polys.densetools.dmp_eval_in(f, a, j, u, K)[source]

Evaluate a polynomial at x_j = a in K[X] using the Horner scheme.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 2*x*y + 3*x + y + 2
>>> R.dmp_eval_in(f, 2, 0)
5*y + 8
>>> R.dmp_eval_in(f, 2, 1)
7*x + 4
diofant.polys.densetools.dmp_eval_tail(f, A, u, K)[source]

Evaluate a polynomial at x_j = a_j, ... in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 2*x*y + 3*x + y + 2
>>> R.dmp_eval_tail(f, [2])
7*x + 4
>>> R.dmp_eval_tail(f, [2, 2])
18
diofant.polys.densetools.dmp_diff_eval_in(f, m, a, j, u, K)[source]

Differentiate and evaluate a polynomial in x_j at a in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1
>>> R.dmp_diff_eval_in(f, 1, 2, 0)
y**2 + 2*y + 3
>>> R.dmp_diff_eval_in(f, 1, 2, 1)
6*x + 11
diofant.polys.densetools.dmp_trunc(f, p, u, K)[source]

Reduce a K[X] polynomial modulo a polynomial p in K[Y].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3
>>> g = (y - 1).drop(x)
>>> R.dmp_trunc(f, g)
11*x**2 + 11*x + 5
diofant.polys.densetools.dmp_ground_trunc(f, p, u, K)[source]

Reduce a K[X] polynomial modulo a constant p in K.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3
>>> R.dmp_ground_trunc(f, ZZ(3))
-x**2 - x*y - y
diofant.polys.densetools.dup_monic(f, K)[source]

Divide all coefficients by LC(f) in K[x].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_monic(3*x**2 + 6*x + 9)
x**2 + 2*x + 3
>>> R, x = ring("x", QQ)
>>> R.dup_monic(3*x**2 + 4*x + 2)
x**2 + 4/3*x + 2/3
diofant.polys.densetools.dmp_ground_monic(f, u, K)[source]

Divide all coefficients by LC(f) in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 3*x**2*y + 6*x**2 + 3*x*y + 9*y + 3
>>> R.dmp_ground_monic(f)
x**2*y + 2*x**2 + x*y + 3*y + 1
>>> R, x, y = ring("x y", QQ)
>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3
>>> R.dmp_ground_monic(f)
x**2*y + 8/3*x**2 + 5/3*x*y + 2*x + 2/3*y + 1
diofant.polys.densetools.dup_content(f, K)[source]

Compute the GCD of coefficients of f in K[x].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> f = 6*x**2 + 8*x + 12
>>> R.dup_content(f)
2
>>> R, x = ring("x", QQ)
>>> f = 6*x**2 + 8*x + 12
>>> R.dup_content(f)
2
diofant.polys.densetools.dmp_ground_content(f, u, K)[source]

Compute the GCD of coefficients of f in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_content(f)
2
>>> R, x, y = ring("x y", QQ)
>>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_content(f)
2
diofant.polys.densetools.dup_primitive(f, K)[source]

Compute content and the primitive form of f in K[x].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> f = 6*x**2 + 8*x + 12
>>> R.dup_primitive(f)
(2, 3*x**2 + 4*x + 6)
>>> R, x = ring("x", QQ)
>>> f = 6*x**2 + 8*x + 12
>>> R.dup_primitive(f)
(2, 3*x**2 + 4*x + 6)
diofant.polys.densetools.dmp_ground_primitive(f, u, K)[source]

Compute content and the primitive form of f in K[X].

Examples

>>> from diofant.domains import ZZ, QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_primitive(f)
(2, x*y + 3*x + 2*y + 6)
>>> R, x, y = ring("x y", QQ)
>>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_primitive(f)
(2, x*y + 3*x + 2*y + 6)
diofant.polys.densetools.dup_extract(f, g, K)[source]

Extract common content from a pair of polynomials in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_extract(6*x**2 + 12*x + 18, 4*x**2 + 8*x + 12)
(2, 3*x**2 + 6*x + 9, 2*x**2 + 4*x + 6)
diofant.polys.densetools.dmp_ground_extract(f, g, u, K)[source]

Extract common content from a pair of polynomials in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_ground_extract(6*x*y + 12*x + 18, 4*x*y + 8*x + 12)
(2, 3*x*y + 6*x + 9, 2*x*y + 4*x + 6)
diofant.polys.densetools.dup_real_imag(f, K)[source]

Return bivariate polynomials f1 and f2, such that f = f1 + f2*I.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dup_real_imag(x**3 + x**2 + x + 1)
(x**3 + x**2 - 3*x*y**2 + x - y**2 + 1, 3*x**2*y + 2*x*y - y**3 + y)
diofant.polys.densetools.dup_mirror(f, K)[source]

Evaluate efficiently the composition f(-x) in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_mirror(x**3 + 2*x**2 - 4*x + 2)
-x**3 + 2*x**2 + 4*x + 2
diofant.polys.densetools.dup_scale(f, a, K)[source]

Evaluate efficiently composition f(a*x) in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_scale(x**2 - 2*x + 1, ZZ(2))
4*x**2 - 4*x + 1
diofant.polys.densetools.dup_shift(f, a, K)[source]

Evaluate efficiently Taylor shift f(x + a) in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_shift(x**2 - 2*x + 1, ZZ(2))
x**2 + 2*x + 1
diofant.polys.densetools.dup_transform(f, p, q, K)[source]

Evaluate functional transformation q**n * f(p/q) in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_transform(x**2 - 2*x + 1, x**2 + 1, x - 1)
x**4 - 2*x**3 + 5*x**2 - 4*x + 4
diofant.polys.densetools.dmp_compose(f, g, u, K)[source]

Evaluate functional composition f(g) in K[X].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_compose(x*y + 2*x + y, y)
y**2 + 3*y
diofant.polys.densetools.dup_decompose(f, K)[source]

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

References

[R22][Kozen89]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_decompose(x**4 - 2*x**3 + x**2)
[x**2, x**2 - x]
diofant.polys.densetools.dmp_lift(f, u, K)[source]

Convert algebraic coefficients to integers in K[X].

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> from diofant.core import I
>>> K = QQ.algebraic_field(I)
>>> R, x = ring("x", K)
>>> f = x**2 + K([QQ(1), QQ(0)])*x + K([QQ(2), QQ(0)])
>>> R.dmp_lift(f)
x**8 + 2*x**6 + 9*x**4 - 8*x**2 + 16
diofant.polys.densetools.dup_sign_variations(f, K)[source]

Compute the number of sign variations of f in K[x].

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_sign_variations(x**4 - x**2 - x + 1)
2
diofant.polys.densetools.dmp_clear_denoms(f, u, K0, K1=None, convert=False)[source]

Clear denominators, i.e. transform K_0 to K_1.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> f = x/2 + y/3 + 1
>>> R.dmp_clear_denoms(f, convert=False)
(6, 3*x + 2*y + 6)
>>> R.dmp_clear_denoms(f, convert=True)
(6, 3*x + 2*y + 6)
diofant.polys.densetools.dmp_revert(f, g, u, K)[source]

Compute f**(-1) mod x**n using Newton iteration.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
diofant.polys.rootisolation.dup_sturm(f, K)[source]

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

Given a univariate, square-free polynomial f(x) returns the associated Sturm sequence 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))

References

[R44][Davenport88]

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x = ring("x", QQ)
>>> R.dup_sturm(x**3 - 2*x**2 + x - 3)
[x**3 - 2*x**2 + x - 3, 3*x**2 - 4*x + 1, 2/9*x + 25/9, -2079/4]

Manipulation of dense, univariate polynomials with finite field coefficients

Functions in this module carry the prefix gf_, referring to the classical name “Galois Fields” for finite fields. Note that many polynomial factorization algorithms work by reduction to the finite field case, so having special implementations for this case is justified both by performance, and by the necessity of certain methods which do not even make sense over general fields.

diofant.polys.galoistools.gf_crt(U, M, K=None)[source]

Chinese Remainder Theorem.

Given a set of integer residues u_0,...,u_n and a set of co-prime integer moduli m_0,...,m_n, returns an integer u, such that u = u_i mod m_i for i = ``0,...,n.

As an example consider a set of residues U = [49, 76, 65] and a set of moduli M = [99, 97, 95]. Then we have:

>>> from diofant.domains import ZZ
>>> from diofant.ntheory.modular import solve_congruence

>>> gf_crt([49, 76, 65], [99, 97, 95], ZZ)
639985

This is the correct result because:

>>> [639985 % m for m in [99, 97, 95]]
[49, 76, 65]

Note: this is a low-level routine with no error checking.

diofant.polys.galoistools.gf_crt1(M, K)[source]

First part of the Chinese Remainder Theorem.

Examples

>>> from diofant.domains import ZZ
>>> gf_crt1([99, 97, 95], ZZ)
(912285, [9215, 9405, 9603], [62, 24, 12])
diofant.polys.galoistools.gf_crt2(U, M, p, E, S, K)[source]

Second part of the Chinese Remainder Theorem.

Examples

>>> from diofant.domains import ZZ
>>> U = [49, 76, 65]
>>> M = [99, 97, 95]
>>> p = 912285
>>> E = [9215, 9405, 9603]
>>> S = [62, 24, 12]
>>> gf_crt2(U, M, p, E, S, ZZ)
639985
diofant.polys.galoistools.gf_int(a, p)[source]

Coerce a mod p to an integer in the range [-p/2, p/2].

Examples

>>> gf_int(2, 7)
2
>>> gf_int(5, 7)
-2
diofant.polys.galoistools.gf_degree(f)[source]

Return the leading degree of f.

Examples

>>> gf_degree([1, 1, 2, 0])
3
>>> gf_degree([])
-1
diofant.polys.galoistools.gf_LC(f, K)[source]

Return the leading coefficient of f.

Examples

>>> from diofant.domains import ZZ
>>> gf_LC([3, 0, 1], ZZ)
3
diofant.polys.galoistools.gf_TC(f, K)[source]

Return the trailing coefficient of f.

Examples

>>> from diofant.domains import ZZ
>>> gf_TC([3, 0, 1], ZZ)
1
diofant.polys.galoistools.gf_strip(f)[source]

Remove leading zeros from f.

Examples

>>> gf_strip([0, 0, 0, 3, 0, 1])
[3, 0, 1]
diofant.polys.galoistools.gf_trunc(f, p)[source]

Reduce all coefficients modulo p.

Examples

>>> gf_trunc([7, -2, 3], 5)
[2, 3, 3]
diofant.polys.galoistools.gf_normal(f, p, K)[source]

Normalize all coefficients in K.

Examples

>>> from diofant.domains import ZZ
>>> gf_normal([5, 10, 21, -3], 5, ZZ)
[1, 2]
diofant.polys.galoistools.gf_from_dict(f, p, K)[source]

Create a GF(p)[x] polynomial from a dict.

Examples

>>> from diofant.domains import ZZ
>>> gf_from_dict({10: ZZ(4), 4: ZZ(33), 0: ZZ(-1)}, 5, ZZ)
[4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4]
diofant.polys.galoistools.gf_to_dict(f, p, symmetric=True)[source]

Convert a GF(p)[x] polynomial to a dict.

Examples

>>> gf_to_dict([4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4], 5)
{0: -1, 4: -2, 10: -1}
>>> gf_to_dict([4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4], 5, symmetric=False)
{0: 4, 4: 3, 10: 4}
diofant.polys.galoistools.gf_from_int_poly(f, p)[source]

Create a GF(p)[x] polynomial from Z[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_from_int_poly([7, -2, 3], 5)
[2, 3, 3]
diofant.polys.galoistools.gf_to_int_poly(f, p, symmetric=True)[source]

Convert a GF(p)[x] polynomial to Z[x].

Examples

>>> gf_to_int_poly([2, 3, 3], 5)
[2, -2, -2]
>>> gf_to_int_poly([2, 3, 3], 5, symmetric=False)
[2, 3, 3]
diofant.polys.galoistools.gf_neg(f, p, K)[source]

Negate a polynomial in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_neg([3, 2, 1, 0], 5, ZZ)
[2, 3, 4, 0]
diofant.polys.galoistools.gf_add_ground(f, a, p, K)[source]

Compute f + a where f in GF(p)[x] and a in GF(p).

Examples

>>> from diofant.domains import ZZ
>>> gf_add_ground([3, 2, 4], 2, 5, ZZ)
[3, 2, 1]
diofant.polys.galoistools.gf_sub_ground(f, a, p, K)[source]

Compute f - a where f in GF(p)[x] and a in GF(p).

Examples

>>> from diofant.domains import ZZ
>>> gf_sub_ground([3, 2, 4], 2, 5, ZZ)
[3, 2, 2]
diofant.polys.galoistools.gf_mul_ground(f, a, p, K)[source]

Compute f * a where f in GF(p)[x] and a in GF(p).

Examples

>>> from diofant.domains import ZZ
>>> gf_mul_ground([3, 2, 4], 2, 5, ZZ)
[1, 4, 3]
diofant.polys.galoistools.gf_quo_ground(f, a, p, K)[source]

Compute f/a where f in GF(p)[x] and a in GF(p).

Examples

>>> from diofant.domains import ZZ
>>> gf_quo_ground(ZZ.map([3, 2, 4]), ZZ(2), 5, ZZ)
[4, 1, 2]
diofant.polys.galoistools.gf_add(f, g, p, K)[source]

Add polynomials in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_add([3, 2, 4], [2, 2, 2], 5, ZZ)
[4, 1]
diofant.polys.galoistools.gf_sub(f, g, p, K)[source]

Subtract polynomials in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_sub([3, 2, 4], [2, 2, 2], 5, ZZ)
[1, 0, 2]
diofant.polys.galoistools.gf_mul(f, g, p, K)[source]

Multiply polynomials in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_mul([3, 2, 4], [2, 2, 2], 5, ZZ)
[1, 0, 3, 2, 3]
diofant.polys.galoistools.gf_sqr(f, p, K)[source]

Square polynomials in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_sqr([3, 2, 4], 5, ZZ)
[4, 2, 3, 1, 1]
diofant.polys.galoistools.gf_add_mul(f, g, h, p, K)[source]

Returns f + g*h where f, g, h in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_add_mul([3, 2, 4], [2, 2, 2], [1, 4], 5, ZZ)
[2, 3, 2, 2]
diofant.polys.galoistools.gf_sub_mul(f, g, h, p, K)[source]

Compute f - g*h where f, g, h in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_sub_mul([3, 2, 4], [2, 2, 2], [1, 4], 5, ZZ)
[3, 3, 2, 1]
diofant.polys.galoistools.gf_expand(F, p, K)[source]

Expand results of factor() in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_expand([([3, 2, 4], 1), ([2, 2], 2), ([3, 1], 3)], 5, ZZ)
[4, 3, 0, 3, 0, 1, 4, 1]
diofant.polys.galoistools.gf_div(f, g, p, K)[source]

Division with remainder in GF(p)[x].

Given univariate polynomials f and g with coefficients in a finite field with p elements, returns polynomials q and r (quotient and remainder) such that f = q*g + r.

Consider polynomials x**3 + x + 1 and x**2 + x in GF(2):

>>> from diofant.domains import ZZ

>>> gf_div(ZZ.map([1, 0, 1, 1]), ZZ.map([1, 1, 0]), 2, ZZ)
([1, 1], [1])

As result we obtained quotient x + 1 and remainder 1, thus:

>>> gf_add_mul(ZZ.map([1]), ZZ.map([1, 1]), ZZ.map([1, 1, 0]), 2, ZZ)
[1, 0, 1, 1]

References

[R67][Monagan93]
[R77][Gathen99]
diofant.polys.galoistools.gf_rem(f, g, p, K)[source]

Compute polynomial remainder in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_rem(ZZ.map([1, 0, 1, 1]), ZZ.map([1, 1, 0]), 2, ZZ)
[1]
diofant.polys.galoistools.gf_quo(f, g, p, K)[source]

Compute exact quotient in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_quo(ZZ.map([1, 0, 1, 1]), ZZ.map([1, 1, 0]), 2, ZZ)
[1, 1]
>>> gf_quo(ZZ.map([1, 0, 3, 2, 3]), ZZ.map([2, 2, 2]), 5, ZZ)
[3, 2, 4]
diofant.polys.galoistools.gf_exquo(f, g, p, K)[source]

Compute polynomial quotient in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_exquo(ZZ.map([1, 0, 3, 2, 3]), ZZ.map([2, 2, 2]), 5, ZZ)
[3, 2, 4]
>>> gf_exquo(ZZ.map([1, 0, 1, 1]), ZZ.map([1, 1, 0]), 2, ZZ)
Traceback (most recent call last):
...
ExactQuotientFailed: [1, 1, 0] does not divide [1, 0, 1, 1]
diofant.polys.galoistools.gf_lshift(f, n, K)[source]

Efficiently multiply f by x**n.

Examples

>>> from diofant.domains import ZZ
>>> gf_lshift([3, 2, 4], 4, ZZ)
[3, 2, 4, 0, 0, 0, 0]
diofant.polys.galoistools.gf_rshift(f, n, K)[source]

Efficiently divide f by x**n.

Examples

>>> from diofant.domains import ZZ
>>> gf_rshift([1, 2, 3, 4, 0], 3, ZZ)
([1, 2], [3, 4, 0])
diofant.polys.galoistools.gf_pow(f, n, p, K)[source]

Compute f**n in GF(p)[x] using repeated squaring.

Examples

>>> from diofant.domains import ZZ
>>> gf_pow([3, 2, 4], 3, 5, ZZ)
[2, 4, 4, 2, 2, 1, 4]
diofant.polys.galoistools.gf_pow_mod(f, n, g, p, K)[source]

Compute f**n in GF(p)[x]/(g) using repeated squaring.

Given polynomials f and g in GF(p)[x] and a non-negative integer n, efficiently computes f**n (mod g) i.e. the remainder of f**n from division by g, using the repeated squaring algorithm.

References

[R1010][Gathen99]

Examples

>>> from diofant.domains import ZZ
>>> gf_pow_mod(ZZ.map([3, 2, 4]), 3, ZZ.map([1, 1]), 5, ZZ)
[]
diofant.polys.galoistools.gf_gcd(f, g, p, K)[source]

Euclidean Algorithm in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_gcd(ZZ.map([3, 2, 4]), ZZ.map([2, 2, 3]), 5, ZZ)
[1, 3]
diofant.polys.galoistools.gf_lcm(f, g, p, K)[source]

Compute polynomial LCM in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_lcm(ZZ.map([3, 2, 4]), ZZ.map([2, 2, 3]), 5, ZZ)
[1, 2, 0, 4]
diofant.polys.galoistools.gf_cofactors(f, g, p, K)[source]

Compute polynomial GCD and cofactors in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_cofactors(ZZ.map([3, 2, 4]), ZZ.map([2, 2, 3]), 5, ZZ)
([1, 3], [3, 3], [2, 1])
diofant.polys.galoistools.gf_gcdex(f, g, p, K)[source]

Extended Euclidean Algorithm in GF(p)[x].

Given polynomials f and g in GF(p)[x], computes polynomials s, t and h, such that h = gcd(f, g) and s*f + t*g = h. The typical application of EEA is solving polynomial diophantine equations.

Consider polynomials f = (x + 7) (x + 1), g = (x + 7) (x**2 + 1) in GF(11)[x]. Application of Extended Euclidean Algorithm gives:

>>> from diofant.domains import ZZ

>>> s, t, g = gf_gcdex(ZZ.map([1, 8, 7]), ZZ.map([1, 7, 1, 7]), 11, ZZ)
>>> (s, t, g)
([5, 6], [6], [1, 7])

As result we obtained polynomials s = 5*x + 6 and t = 6, and additionally gcd(f, g) = x + 7. This is correct because:

>>> S = gf_mul(s, ZZ.map([1, 8, 7]), 11, ZZ)
>>> T = gf_mul(t, ZZ.map([1, 7, 1, 7]), 11, ZZ)

>>> gf_add(S, T, 11, ZZ)
[1, 7]

References

[R1212][Gathen99]
diofant.polys.galoistools.gf_monic(f, p, K)[source]

Compute LC and a monic polynomial in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_monic(ZZ.map([3, 2, 4]), 5, ZZ)
(3, [1, 4, 3])
diofant.polys.galoistools.gf_diff(f, p, K)[source]

Differentiate polynomial in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_diff([3, 2, 4], 5, ZZ)
[1, 2]
diofant.polys.galoistools.gf_eval(f, a, p, K)[source]

Evaluate f(a) in GF(p) using Horner scheme.

Examples

>>> from diofant.domains import ZZ
>>> gf_eval([3, 2, 4], 2, 5, ZZ)
0
diofant.polys.galoistools.gf_multi_eval(f, A, p, K)[source]

Evaluate f(a) for a in [a_1, ..., a_n].

Examples

>>> from diofant.domains import ZZ
>>> gf_multi_eval([3, 2, 4], [0, 1, 2, 3, 4], 5, ZZ)
[4, 4, 0, 2, 0]
diofant.polys.galoistools.gf_compose(f, g, p, K)[source]

Compute polynomial composition f(g) in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_compose([3, 2, 4], [2, 2, 2], 5, ZZ)
[2, 4, 0, 3, 0]
diofant.polys.galoistools.gf_compose_mod(g, h, f, p, K)[source]

Compute polynomial composition g(h) in GF(p)[x]/(f).

Examples

>>> from diofant.domains import ZZ
>>> gf_compose_mod(ZZ.map([3, 2, 4]), ZZ.map([2, 2, 2]), ZZ.map([4, 3]), 5, ZZ)
[4]
diofant.polys.galoistools.gf_trace_map(a, b, c, n, f, p, K)[source]

Compute polynomial trace map in GF(p)[x]/(f).

Given a polynomial f in GF(p)[x], polynomials a, b, c in the quotient ring GF(p)[x]/(f) such that b = c**t (mod f) for some positive power t of p, and a positive integer n, returns a mapping:

a -> a**t**n, a + a**t + a**t**2 + ... + a**t**n (mod f)

In factorization context, b = x**p mod f and c = x mod f. This way we can efficiently compute trace polynomials in equal degree factorization routine, much faster than with other methods, like iterated Frobenius algorithm, for large degrees.

References

[R1414][Gathen92]

Examples

>>> from diofant.domains import ZZ
>>> gf_trace_map([1, 2], [4, 4], [1, 1], 4, [3, 2, 4], 5, ZZ)
([1, 3], [1, 3])
diofant.polys.galoistools.gf_random(n, p, K)[source]

Generate a random polynomial in GF(p)[x] of degree n.

Examples

>>> from diofant.domains import ZZ
>>> gf_random(10, 5, ZZ) 
[1, 2, 3, 2, 1, 1, 1, 2, 0, 4, 2]
diofant.polys.galoistools.gf_irreducible(n, p, K)[source]

Generate random irreducible polynomial of degree n in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_irreducible(10, 5, ZZ) 
[1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4]
diofant.polys.galoistools.gf_irreducible_p(f, p, K)[source]

Test irreducibility of a polynomial f in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_irreducible_p(ZZ.map([1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4]), 5, ZZ)
True
>>> gf_irreducible_p(ZZ.map([3, 2, 4]), 5, ZZ)
False
diofant.polys.galoistools.gf_sqf_p(f, p, K)[source]

Return True if f is square-free in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_sqf_p(ZZ.map([3, 2, 4]), 5, ZZ)
True
>>> gf_sqf_p(ZZ.map([2, 4, 4, 2, 2, 1, 4]), 5, ZZ)
False
diofant.polys.galoistools.gf_sqf_part(f, p, K)[source]

Return square-free part of a GF(p)[x] polynomial.

Examples

>>> from diofant.domains import ZZ
>>> gf_sqf_part(ZZ.map([1, 1, 3, 0, 1, 0, 2, 2, 1]), 5, ZZ)
[1, 4, 3]
diofant.polys.galoistools.gf_sqf_list(f, p, K, all=False)[source]

Return the square-free decomposition of a GF(p)[x] polynomial.

Given a polynomial f in GF(p)[x], returns the leading coefficient of f and a square-free decomposition f_1**e_1 f_2**e_2 ... f_k**e_k such that all f_i are monic polynomials and (f_i, f_j) for i != j are co-prime and e_1 ... e_k are given in increasing order. All trivial terms (i.e. f_i = 1) aren’t included in the output.

Consider polynomial f = x**11 + 1 over GF(11)[x]:

>>> from diofant.domains import ZZ

>>> f = gf_from_dict({11: ZZ(1), 0: ZZ(1)}, 11, ZZ)

Note that f'(x) = 0:

>>> gf_diff(f, 11, ZZ)
[]

This phenomenon doesn’t happen in characteristic zero. However we can still compute square-free decomposition of f using gf_sqf():

>>> gf_sqf_list(f, 11, ZZ)
(1, [([1, 1], 11)])

We obtained factorization f = (x + 1)**11. This is correct because:

>>> gf_pow([1, 1], 11, 11, ZZ) == f
True

References

[R1616][Geddes92]
diofant.polys.galoistools.gf_Qmatrix(f, p, K)[source]

Calculate Berlekamp’s Q matrix.

Examples

>>> from diofant.domains import ZZ
>>> gf_Qmatrix([3, 2, 4], 5, ZZ)
[[1, 0],
 [3, 4]]
>>> gf_Qmatrix([1, 0, 0, 0, 1], 5, ZZ)
[[1, 0, 0, 0],
 [0, 4, 0, 0],
 [0, 0, 1, 0],
 [0, 0, 0, 4]]
diofant.polys.galoistools.gf_Qbasis(Q, p, K)[source]

Compute a basis of the kernel of Q.

Examples

>>> from diofant.domains import ZZ
>>> gf_Qbasis(gf_Qmatrix([1, 0, 0, 0, 1], 5, ZZ), 5, ZZ)
[[1, 0, 0, 0], [0, 0, 1, 0]]
>>> gf_Qbasis(gf_Qmatrix([3, 2, 4], 5, ZZ), 5, ZZ)
[[1, 0]]
diofant.polys.galoistools.gf_berlekamp(f, p, K)[source]

Factor a square-free f in GF(p)[x] for small p.

Examples

>>> from diofant.domains import ZZ
>>> gf_berlekamp([1, 0, 0, 0, 1], 5, ZZ)
[[1, 0, 2], [1, 0, 3]]
diofant.polys.galoistools.gf_zassenhaus(f, p, K)[source]

Factor a square-free f in GF(p)[x] for medium p.

Examples

>>> from diofant.domains import ZZ
>>> gf_zassenhaus(ZZ.map([1, 4, 3]), 5, ZZ)
[[1, 1], [1, 3]]
diofant.polys.galoistools.gf_shoup(f, p, K)[source]

Factor a square-free f in GF(p)[x] for large p.

Examples

>>> from diofant.domains import ZZ
>>> gf_shoup(ZZ.map([1, 4, 3]), 5, ZZ)
[[1, 1], [1, 3]]
diofant.polys.galoistools.gf_ddf_shoup(f, p, K)[source]

Kaltofen-Shoup: Deterministic Distinct Degree Factorization

Given a monic square-free polynomial f in GF(p)[x], computes partial distinct degree factorization f_1,...,f_d of f where deg(f_i) != deg(f_j) for i != j. The result is returned as a list of pairs (f_i, e_i) where deg(f_i) > 0 and e_i > 0 is an argument to the equal degree factorization routine.

This algorithm is an improved version of Zassenhaus algorithm for large deg(f) and modulus p (especially for deg(f) ~ lg(p)).

References

[R1820][Kaltofen98]
[R1920][Shoup95]
[R2020][Gathen92]

Examples

>>> from diofant.domains import ZZ
>>> f = gf_from_dict({6: ZZ(1), 5: ZZ(-1), 4: ZZ(1), 3: ZZ(1), 1: ZZ(-1)}, 3, ZZ)
>>> gf_ddf_shoup(f, 3, ZZ)
[([1, 1, 0], 1), ([1, 1, 0, 1, 2], 2)]
diofant.polys.galoistools.gf_factor_sqf(f, p, K)[source]

Factor a square-free polynomial f in GF(p)[x].

Examples

>>> from diofant.domains import ZZ
>>> gf_factor_sqf(ZZ.map([3, 2, 4]), 5, ZZ)
(3, [[1, 1], [1, 3]])
diofant.polys.galoistools.gf_factor(f, p, K)[source]

Factor (non square-free) polynomials in GF(p)[x].

Given a possibly non square-free polynomial f in GF(p)[x], returns its complete factorization into irreducibles:

f_1(x)**e_1 f_2(x)**e_2 ... f_d(x)**e_d

where each f_i is a monic polynomial and gcd(f_i, f_j) == 1, for i != j. The result is given as a tuple consisting of the leading coefficient of f and a list of factors of f with their multiplicities.

The algorithm proceeds by first computing square-free decomposition of f and then iteratively factoring each of square-free factors.

Consider a non square-free polynomial f = (7*x + 1) (x + 2)**2 in GF(11)[x]. We obtain its factorization into irreducibles as follows:

>>> from diofant.domains import ZZ

>>> gf_factor(ZZ.map([5, 2, 7, 2]), 11, ZZ)
(5, [([1, 2], 1), ([1, 8], 2)])

We arrived with factorization f = 5 (x + 2) (x + 8)**2. We didn’t recover the exact form of the input polynomial because we requested to get monic factors of f and its leading coefficient separately.

Square-free factors of f can be factored into irreducibles over GF(p) using three very different methods:

Berlekamp
efficient for very small values of p (usually p < 25)
Cantor-Zassenhaus
efficient on average input and with “typical” p
Shoup-Kaltofen-Gathen
efficient with very large inputs and modulus

If you want to use a specific factorization method, instead of the default one, set GF_FACTOR_METHOD with one of berlekamp, zassenhaus or shoup values.

References

[R2424][Gathen99]
diofant.polys.galoistools.gf_value(f, a)[source]

Value of polynomial ‘f’ at ‘a’ in field R.

Examples

>>> gf_value([1, 7, 2, 4], 11)
2204
diofant.polys.galoistools.gf_csolve(f, n)[source]

To solve f(x) congruent 0 mod(n).

n is divided into canonical factors and f(x) cong 0 mod(p**e) will be solved for each factor. Applying the Chinese Remainder Theorem to the results returns the final answers.

References

[R2626]‘An introduction to the Theory of Numbers’ 5th Edition by Ivan Niven, Zuckerman and Montgomery.

Examples

Solve [1, 1, 7] congruent 0 mod(189):

>>> gf_csolve([1, 1, 7], 189)
[13, 49, 76, 112, 139, 175]
diofant.polys.galoistools.gf_irred_p_ben_or(f, p, K)[source]

Ben-Or’s polynomial irreducibility test over finite fields.

References

[R2828][BenOr81]

Examples

>>> from diofant.domains import ZZ
>>> gf_irred_p_ben_or(ZZ.map([1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4]), 5, ZZ)
True
>>> gf_irred_p_ben_or(ZZ.map([3, 2, 4]), 5, ZZ)
False
diofant.polys.galoistools.gf_edf_shoup(f, n, p, K)[source]

Gathen-Shoup: Probabilistic Equal Degree Factorization

Given a monic square-free polynomial f in GF(p)[x] and integer n such that n divides deg(f), returns all irreducible factors f_1,...,f_d of f, each of degree n. This is a complete factorization over Galois fields.

This algorithm is an improved version of Zassenhaus algorithm for large deg(f) and modulus p (especially for deg(f) ~ lg(p)).

References

[R3031][Shoup91]
[R3131][Gathen92]

Examples

>>> from diofant.domains import ZZ
>>> gf_edf_shoup(ZZ.map([1, 2837, 2277]), 1, 2917, ZZ)
[[1, 852], [1, 1985]]

Manipulation of sparse, distributed polynomials and vectors

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

>>> from diofant.domains import ZZ
>>> from diofant.polys.orderings import lex
>>> R, x, y, z = ring("x y z", ZZ, lex)
>>> R
Polynomial ring in x, y, z over ZZ with lex order
>>> x + y + z
x + y + z
>>> type(_)
<class 'diofant.polys.rings.PolyElement'>
diofant.polys.rings.vring(symbols, domain, order=<diofant.polys.orderings.LexOrder object>)[source]

Construct a polynomial ring and inject x_1, ..., x_n into the global namespace.

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

>>> from diofant.domains import ZZ
>>> from diofant.polys.orderings import lex
>>> vring("x y z", ZZ, lex)
Polynomial ring in x, y, z over ZZ with lex order
>>> x + y + z
x + y + z
>>> type(_)
<class 'diofant.polys.rings.PolyElement'>
diofant.polys.rings.sring(exprs, *symbols, **options)[source]

Construct a ring deriving generators and domain from options and input expressions.

Parameters:

exprs : Expr or sequence of Expr (sympifiable)

symbols : sequence of Symbol/Expr

options : keyword arguments understood by Options

Examples

>>> from diofant.core import symbols
>>> from diofant.domains import ZZ
>>> from diofant.polys.orderings import lex
>>> x, y, z = symbols("x y z")
>>> R, f = sring(x + 2*y + 3*z)
>>> R
Polynomial ring in x, y, z over ZZ with lex order
>>> f
x + 2*y + 3*z
>>> type(_)
<class 'diofant.polys.rings.PolyElement'>
class diofant.polys.rings.PolyRing[source]

Multivariate distributed polynomial ring.

add(*objs)[source]

Add a sequence of polynomials or containers of polynomials.

Examples

>>> from diofant.domains import ZZ
>>> R, x = ring("x", ZZ)
>>> R.add([x**2 + 2*i + 3 for i in range(4)])
4*x**2 + 24
>>> _.factor_list()
(4, [(x**2 + 6, 1)])
drop(*gens)[source]

Remove specified generators from this ring.

drop_to_ground(*gens)[source]

Remove specified generators from the ring and inject them into its domain.

index(gen)[source]

Compute index of gen in self.gens.

monomial_basis(i)[source]

Return the ith-basis element.

mul(*objs)[source]

Multiply a sequence of polynomials or containers of polynomials.

Examples

>>> from diofant.domains import ZZ
>>> R, x = ring("x", ZZ)
>>> R.mul([x**2 + 2*i + 3 for i in range(4)])
x**8 + 24*x**6 + 206*x**4 + 744*x**2 + 945
>>> _.factor_list()
(1, [(x**2 + 3, 1), (x**2 + 5, 1), (x**2 + 7, 1), (x**2 + 9, 1)])
class diofant.polys.rings.PolyElement[source]

Element of multivariate distributed polynomial ring.

almosteq(other, tolerance=None)[source]

Approximate equality test for polynomials.

cancel(g)[source]

Cancel common factors in a rational function f/g.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> (2*x**2 - 2).cancel(x**2 - 2*x + 1)
(2*x + 2, x - 1)
coeff(element)[source]

Returns the coefficient that stands next to the given monomial.

Parameters:element : PolyElement (with is_monomial = True) or 1

Examples

>>> from diofant.domains import ZZ
>>> _, x, y, z = ring("x y z", ZZ)
>>> f = 3*x**2*y - x*y*z + 7*z**3 + 23
>>> f.coeff(x**2*y)
3
>>> f.coeff(x*y)
0
>>> f.coeff(1)
23
coeffs(order=None)[source]

Ordered list of polynomial coefficients.

Parameters:order : Order or coercible, optional

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys.orderings import lex, grlex
>>> _, x, y = ring("x, y", ZZ, lex)
>>> f = x*y**7 + 2*x**2*y**3
>>> f.coeffs()
[2, 1]
>>> f.coeffs(grlex)
[1, 2]
compose(x, a=None)[source]

Computes the functional composition.

const()[source]

Returns the constant coefficient.

content()[source]

Returns GCD of polynomial’s coefficients.

copy()[source]

Return a copy of polynomial self.

Polynomials are mutable; if one is interested in preserving a polynomial, and one plans to use inplace operations, one can copy the polynomial. This method makes a shallow copy.

Examples

>>> from diofant.domains import ZZ
>>> R, x, y = ring('x, y', ZZ)
>>> p = (x + y)**2
>>> p1 = p.copy()
>>> p2 = p
>>> p[R.zero_monom] = 3
>>> p
x**2 + 2*x*y + y**2 + 3
>>> p1
x**2 + 2*x*y + y**2
>>> p2
x**2 + 2*x*y + y**2 + 3
degree(x=None)[source]

The leading degree in x or the main variable.

Note that the degree of 0 is negative infinity (the Diofant object -oo).

degrees()[source]

A tuple containing leading degrees in all variables.

Note that the degree of 0 is negative infinity (the Diofant object -oo)

diff(x)[source]

Computes partial derivative in x.

Examples

>>> from diofant.domains import ZZ
>>> _, x, y = ring("x y", ZZ)
>>> p = x + x**2*y**3
>>> p.diff(x)
2*x*y**3 + 1
div(fv)[source]

Division algorithm, see [CLO] p64.

fv array of polynomials
return qv, r such that self = sum(fv[i]*qv[i]) + r

All polynomials are required not to be Laurent polynomials.

Examples

>>> from diofant.domains import ZZ
>>> _, x, y = ring('x, y', ZZ)
>>> f = x**3
>>> f0 = x - y**2
>>> f1 = x - y
>>> qv, r = f.div((f0, f1))
>>> qv[0]
x**2 + x*y**2 + y**4
>>> qv[1]
0
>>> r
y**6
imul_num(c)[source]

multiply inplace the polynomial self by an element in the coefficient ring, provided self is not one of the generators; else multiply not inplace

Examples

>>> from diofant.domains import ZZ
>>> _, x, y = ring('x, y', ZZ)
>>> p = x + y**2
>>> p1 = p.imul_num(3)
>>> p1
3*x + 3*y**2
>>> p1 is p
True
>>> p = x
>>> p1 = p.imul_num(3)
>>> p1
3*x
>>> p1 is p
False
itercoeffs()[source]

Iterator over coefficients of a polynomial.

itermonoms()[source]

Iterator over monomials of a polynomial.

iterterms()[source]

Iterator over terms of a polynomial.

leading_expv()[source]

Leading monomial tuple according to the monomial ordering.

Examples

>>> from diofant.domains import ZZ
>>> _, 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_monom()[source]

Leading monomial as a polynomial element.

Examples

>>> from diofant.domains import ZZ
>>> _, x, y = ring('x, y', ZZ)
>>> (3*x*y + y**2).leading_monom()
x*y
leading_term()[source]

Leading term as a polynomial element.

Examples

>>> from diofant.domains import ZZ
>>> _, x, y = ring('x, y', ZZ)
>>> (3*x*y + y**2).leading_term()
3*x*y
listcoeffs()[source]

Unordered list of polynomial coefficients.

listmonoms()[source]

Unordered list of polynomial monomials.

listterms()[source]

Unordered list of polynomial terms.

monic()[source]

Divides all coefficients by the leading coefficient.

monoms(order=None)[source]

Ordered list of polynomial monomials.

Parameters:order : Order or coercible, optional

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys.orderings import lex, grlex
>>> _, x, y = ring("x, y", ZZ, lex)
>>> f = x*y**7 + 2*x**2*y**3
>>> f.monoms()
[(2, 3), (1, 7)]
>>> f.monoms(grlex)
[(1, 7), (2, 3)]
primitive()[source]

Returns content and a primitive polynomial.

square()[source]

square of a polynomial

Examples

>>> from diofant.domains import ZZ
>>> _, x, y = ring('x, y', ZZ)
>>> p = x + y**2
>>> p.square()
x**2 + 2*x*y**2 + y**4
strip_zero()[source]

Eliminate monomials with zero coefficient.

tail_degree(x=None)[source]

The tail degree in x or the main variable.

Note that the degree of 0 is negative infinity (the Diofant object -oo)

tail_degrees()[source]

A tuple containing tail degrees in all variables.

Note that the degree of 0 is negative infinity (the Diofant object -oo)

terms(order=None)[source]

Ordered list of polynomial terms.

Parameters:order : Order or coercible, optional

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys.orderings import lex, grlex
>>> _, x, y = ring("x, y", ZZ, lex)
>>> f = x*y**7 + 2*x**2*y**3
>>> f.terms()
[((2, 3), 2), ((1, 7), 1)]
>>> f.terms(grlex)
[((1, 7), 1), ((2, 3), 2)]

In commutative algebra, one often studies not only polynomials, but also modules over polynomial rings. The polynomial manipulation module provides rudimentary low-level support for finitely generated free modules. This is mainly used for Gröbner basis computations (see there), so manipulation functions are only provided to the extend needed. They carry the prefix sdm_. Note that in examples, the generators of the free module are called \(f_1, f_2, \ldots\).

diofant.polys.distributedmodules.sdm_monomial_mul(M, X)[source]

Multiply tuple X representing a monomial of \(K[X]\) into the tuple M representing a monomial of \(F\).

Examples

Multiplying \(xy^3\) into \(x f_1\) yields \(x^2 y^3 f_1\):

>>> sdm_monomial_mul((1, 1, 0), (1, 3))
(1, 2, 3)
diofant.polys.distributedmodules.sdm_monomial_deg(M)[source]

Return the total degree of M.

Examples

For example, the total degree of \(x^2 y f_5\) is 3:

>>> sdm_monomial_deg((5, 2, 1))
3
diofant.polys.distributedmodules.sdm_monomial_divides(A, B)[source]

Does there exist a (polynomial) monomial X such that XA = B?

Examples

Positive examples:

In the following examples, the monomial is given in terms of x, y and the generator(s), f_1, f_2 etc. The tuple form of that monomial is used in the call to sdm_monomial_divides. Note: the generator appears last in the expression but first in the tuple and other factors appear in the same order that they appear in the monomial expression.

\(A = f_1\) divides \(B = f_1\)

>>> sdm_monomial_divides((1, 0, 0), (1, 0, 0))
True

\(A = f_1\) divides \(B = x^2 y f_1\)

>>> sdm_monomial_divides((1, 0, 0), (1, 2, 1))
True

\(A = xy f_5\) divides \(B = x^2 y f_5\)

>>> sdm_monomial_divides((5, 1, 1), (5, 2, 1))
True

Negative examples:

\(A = f_1\) does not divide \(B = f_2\)

>>> sdm_monomial_divides((1, 0, 0), (2, 0, 0))
False

\(A = x f_1\) does not divide \(B = f_1\)

>>> sdm_monomial_divides((1, 1, 0), (1, 0, 0))
False

\(A = xy^2 f_5\) does not divide \(B = y f_5\)

>>> sdm_monomial_divides((5, 1, 2), (5, 0, 1))
False
diofant.polys.distributedmodules.sdm_LC(f, K)[source]

Returns the leading coefficient of f.

diofant.polys.distributedmodules.sdm_to_dict(f)[source]

Make a dictionary from a distributed polynomial.

diofant.polys.distributedmodules.sdm_from_dict(d, O)[source]

Create an sdm from a dictionary.

Here O is the monomial order to use.

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> dic = {(1, 1, 0): QQ(1), (1, 0, 0): QQ(2), (0, 1, 0): QQ(0)}
>>> sdm_from_dict(dic, lex)
[((1, 1, 0), 1), ((1, 0, 0), 2)]
diofant.polys.distributedmodules.sdm_add(f, g, O, K)[source]

Add two module elements f, g.

Addition is done over the ground field K, monomials are ordered according to O.

Examples

All examples use lexicographic order.

\((xy f_1) + (f_2) = f_2 + xy f_1\)

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> sdm_add([((1, 1, 1), QQ(1))], [((2, 0, 0), QQ(1))], lex, QQ)
[((2, 0, 0), 1), ((1, 1, 1), 1)]

\((xy f_1) + (-xy f_1)\) = 0`

>>> sdm_add([((1, 1, 1), QQ(1))], [((1, 1, 1), QQ(-1))], lex, QQ)
[]

\((f_1) + (2f_1) = 3f_1\)

>>> sdm_add([((1, 0, 0), QQ(1))], [((1, 0, 0), QQ(2))], lex, QQ)
[((1, 0, 0), 3)]

\((yf_1) + (xf_1) = xf_1 + yf_1\)

>>> sdm_add([((1, 0, 1), QQ(1))], [((1, 1, 0), QQ(1))], lex, QQ)
[((1, 1, 0), 1), ((1, 0, 1), 1)]
diofant.polys.distributedmodules.sdm_LM(f)[source]

Returns the leading monomial of f.

Only valid if \(f \ne 0\).

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> dic = {(1, 2, 3): QQ(1), (4, 0, 0): QQ(1), (4, 0, 1): QQ(1)}
>>> sdm_LM(sdm_from_dict(dic, lex))
(4, 0, 1)
diofant.polys.distributedmodules.sdm_LT(f)[source]

Returns the leading term of f.

Only valid if \(f \ne 0\).

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> dic = {(1, 2, 3): QQ(1), (4, 0, 0): QQ(2), (4, 0, 1): QQ(3)}
>>> sdm_LT(sdm_from_dict(dic, lex))
((4, 0, 1), 3)
diofant.polys.distributedmodules.sdm_mul_term(f, term, O, K)[source]

Multiply a distributed module element f by a (polynomial) term term.

Multiplication of coefficients is done over the ground field K, and monomials are ordered according to O.

Examples

\(0 f_1 = 0\)

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> sdm_mul_term([((1, 0, 0), QQ(1))], ((0, 0), QQ(0)), lex, QQ)
[]

\(x 0 = 0\)

>>> sdm_mul_term([], ((1, 0), QQ(1)), lex, QQ)
[]

\((x) (f_1) = xf_1\)

>>> sdm_mul_term([((1, 0, 0), QQ(1))], ((1, 0), QQ(1)), lex, QQ)
[((1, 1, 0), 1)]

\((2xy) (3x f_1 + 4y f_2) = 8xy^2 f_2 + 6x^2y f_1\)

>>> f = [((2, 0, 1), QQ(4)), ((1, 1, 0), QQ(3))]
>>> sdm_mul_term(f, ((1, 1), QQ(2)), lex, QQ)
[((2, 1, 2), 8), ((1, 2, 1), 6)]
diofant.polys.distributedmodules.sdm_zero()[source]

Return the zero module element.

diofant.polys.distributedmodules.sdm_deg(f)[source]

Degree of f.

This is the maximum of the degrees of all its monomials. Invalid if f is zero.

Examples

>>> sdm_deg([((1, 2, 3), 1), ((10, 0, 1), 1), ((2, 3, 4), 4)])
7
diofant.polys.distributedmodules.sdm_from_vector(vec, O, K, **opts)[source]

Create an sdm from an iterable of expressions.

Coefficients are created in the ground field K, and terms are ordered according to monomial order O. Named arguments are passed on to the polys conversion code and can be used to specify for example generators.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> from diofant.abc import x, y, z
>>> sdm_from_vector([x**2+y**2, 2*z], lex, QQ)
[((1, 0, 0, 1), 2), ((0, 2, 0, 0), 1), ((0, 0, 2, 0), 1)]
diofant.polys.distributedmodules.sdm_to_vector(f, gens, K, n=None)[source]

Convert sdm f into a list of polynomial expressions.

The generators for the polynomial ring are specified via gens. The rank of the module is guessed, or passed via n. The ground field is assumed to be K.

Examples

>>> from diofant.domains import QQ
>>> from diofant.abc import x, y, z
>>> f = [((1, 0, 0, 1), QQ(2)), ((0, 2, 0, 0), QQ(1)), ((0, 0, 2, 0), QQ(1))]
>>> sdm_to_vector(f, [x, y, z], QQ)
[x**2 + y**2, 2*z]

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.

diofant.polys.euclidtools.dmp_half_gcdex(f, g, u, K)[source]

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

diofant.polys.euclidtools.dmp_gcdex(f, g, u, K)[source]

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

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.

diofant.polys.euclidtools.dup_primitive_prs(f, g, K)[source]

Primitive polynomial remainder sequence (PRS) in \(K[x]\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> f = x**8 + x**6 - 3*x**4 - 3*x**3 + 8*x**2 + 2*x - 5
>>> g = 3*x**6 + 5*x**4 - 4*x**2 - 9*x + 21
>>> prs = R.dup_primitive_prs(f, g)
>>> prs[0]
x**8 + x**6 - 3*x**4 - 3*x**3 + 8*x**2 + 2*x - 5
>>> prs[1]
3*x**6 + 5*x**4 - 4*x**2 - 9*x + 21
>>> prs[2]
-5*x**4 + x**2 - 3
>>> prs[3]
13*x**2 + 25*x - 49
>>> prs[4]
4663*x - 6150
>>> prs[5]
1

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 [Collins67] 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 [BrownTraub71] 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 [Brown78] 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.

diofant.polys.euclidtools.dmp_inner_subresultants(f, g, u, K)[source]

Subresultant PRS algorithm in \(K[X]\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, 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
>>> prs = [f, g, a, b]
>>> sres = [[1], [1], [3, 0, 0, 0, 0], [-3, 0, 0, -12, 1, 0, -54, 8, 729, -216, 16]]
>>> R.dmp_inner_subresultants(f, g) == (prs, sres)
True
diofant.polys.euclidtools.dmp_subresultants(f, g, u, K)[source]

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

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, 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
>>> R.dmp_subresultants(f, g) == [f, g, a, b]
True
diofant.polys.euclidtools.dmp_prs_resultant(f, g, u, K)[source]

Resultant algorithm in \(K[X]\) using subresultant PRS.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, 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
>>> res, prs = R.dmp_prs_resultant(f, g)
>>> res == b             # resultant has n-1 variables
False
>>> res == b.drop(x)
True
>>> prs == [f, g, a, b]
True
diofant.polys.euclidtools.dmp_zz_modular_resultant(f, g, p, u, K)[source]

Compute resultant of \(f\) and \(g\) modulo a prime \(p\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x + y + 2
>>> g = 2*x*y + x + 3
>>> R.dmp_zz_modular_resultant(f, g, 5)
-2*y**2 + 1
diofant.polys.euclidtools.dmp_zz_collins_resultant(f, g, u, K)[source]

Collins’s modular resultant algorithm in \(Z[X]\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x + y + 2
>>> g = 2*x*y + x + 3
>>> R.dmp_zz_collins_resultant(f, g)
-2*y**2 - 5*y + 1
diofant.polys.euclidtools.dmp_qq_collins_resultant(f, g, u, K0)[source]

Collins’s modular resultant algorithm in \(Q[X]\).

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> f = x/2 + y + QQ(2, 3)
>>> g = 2*x*y + x + 3
>>> R.dmp_qq_collins_resultant(f, g)
-2*y**2 - 7/3*y + 5/6
diofant.polys.euclidtools.dmp_resultant(f, g, u, K, includePRS=False)[source]

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

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9
>>> R.dmp_resultant(f, g)
-3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16
diofant.polys.euclidtools.dmp_discriminant(f, u, K)[source]

Computes discriminant of a polynomial in \(K[X]\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y, z, t = ring("x y z t", ZZ)
>>> R.dmp_discriminant(x**2*y + x*z + t)
-4*y*t + z**2
diofant.polys.euclidtools.dmp_rr_prs_gcd(f, g, u, K)[source]

Computes polynomial GCD using subresultants over a ring.

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y
>>> R.dmp_rr_prs_gcd(f, g)
(x + y, x + y, x)
diofant.polys.euclidtools.dmp_ff_prs_gcd(f, g, u, K)[source]

Computes polynomial GCD using subresultants over a field.

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> f = x**2/2 + x*y + y**2/2
>>> g = x**2 + x*y
>>> R.dmp_ff_prs_gcd(f, g)
(x + y, 1/2*x + 1/2*y, x)
diofant.polys.euclidtools.dmp_zz_heu_gcd(f, g, u, K)[source]

Heuristic polynomial GCD in \(Z[X]\).

Given univariate polynomials \(f\) and \(g\) in \(Z[X]\), returns their GCD and cofactors, i.e. polynomials h, cff and cfg such that:

h = gcd(f, g), cff = quo(f, h) and cfg = quo(g, h)

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. This gives cofactors of the input polynomials as a side effect.

References

[R3434][Liao95]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y
>>> R.dmp_zz_heu_gcd(f, g)
(x + y, x + y, x)
diofant.polys.euclidtools.dmp_qq_heu_gcd(f, g, u, K0)[source]

Heuristic polynomial GCD in \(Q[X]\).

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", QQ)
>>> f = x**2/4 + x*y + y**2
>>> g = x**2/2 + x*y
>>> R.dmp_qq_heu_gcd(f, g)
(x + 2*y, 1/4*x + 1/2*y, 1/2*x)
diofant.polys.euclidtools.dmp_inner_gcd(f, g, u, K)[source]

Computes polynomial GCD and cofactors of \(f\) and \(g\) in \(K[X]\).

Returns (h, cff, cfg) such that a = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y
>>> R.dmp_inner_gcd(f, g)
(x + y, x + y, x)
diofant.polys.euclidtools.dmp_gcd(f, g, u, K)[source]

Computes polynomial GCD of \(f\) and \(g\) in \(K[X]\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y
>>> R.dmp_gcd(f, g)
x + y
diofant.polys.euclidtools.dmp_lcm(f, g, u, K)[source]

Computes polynomial LCM of \(f\) and \(g\) in \(K[X]\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> f = x**2 + 2*x*y + y**2
>>> g = x**2 + x*y
>>> R.dmp_lcm(f, g)
x**3 + 2*x**2*y + x*y**2
diofant.polys.euclidtools.dmp_content(f, u, K)[source]

Returns GCD of multivariate coefficients.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_content(2*x*y + 6*x + 4*y + 12)
2*y + 6
diofant.polys.euclidtools.dmp_primitive(f, u, K)[source]

Returns multivariate content and a primitive polynomial.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_primitive(2*x*y + 6*x + 4*y + 12)
(2*y + 6, x + 2)
diofant.polys.euclidtools.dmp_cancel(f, g, u, K, include=True)[source]

Cancel common factors in a rational function \(f/g\).

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_cancel(2*x**2 - 2, x**2 - 2*x + 1)
(2*x + 2, x - 1)

Polynomial factorization in characteristic zero:

diofant.polys.factortools.dmp_trial_division(f, factors, u, K)[source]

Determine multiplicities of factors using trial division.

diofant.polys.factortools.dmp_zz_mignotte_bound(f, u, K)[source]

Mignotte bound for multivariate polynomials in \(K[X]\).

diofant.polys.factortools.dup_zz_hensel_step(m, f, g, h, s, t, K)[source]

One step in Hensel lifting in \(Z[x]\).

Given positive integer \(m\) and \(Z[x]\) polynomials \(f\), \(g\), \(h\), \(s\) and \(t\) such that:

f == g*h (mod m)
s*g + t*h == 1 (mod m)

lc(f) is not a zero divisor (mod m)
lc(h) == 1

deg(f) == deg(g) + deg(h)
deg(s) < deg(h)
deg(t) < deg(g)

returns polynomials \(G\), \(H\), \(S\) and \(T\), such that:

f == G*H (mod m**2)
S*G + T**H == 1 (mod m**2)

References

[R3636][Gathen99]
diofant.polys.factortools.dup_zz_hensel_lift(p, f, f_list, l, K)[source]

Multifactor Hensel lifting in \(Z[x]\).

Given a prime \(p\), polynomial \(f\) over \(Z[x]\) such that \(lc(f)\) is a unit modulo \(p\), monic pair-wise coprime polynomials \(f_i\) over \(Z[x]\) satisfying:

f = lc(f) f_1 ... f_r (mod p)

and a positive integer \(l\), returns a list of monic polynomials \(F_1\), \(F_2\), …, \(F_r\) satisfying:

f = lc(f) F_1 ... F_r (mod p**l)

F_i = f_i (mod p), i = 1..r

References

[R3838][Gathen99]
diofant.polys.factortools.dup_zz_zassenhaus(f, K)[source]

Factor primitive square-free polynomials in \(Z[x]\).

diofant.polys.factortools.dup_zz_irreducible_p(f, K)[source]

Test irreducibility using Eisenstein’s criterion.

diofant.polys.factortools.dup_cyclotomic_p(f, K, irreducible=False)[source]

Efficiently test if f is a cyclotomic polynomial.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> f = x**16 + x**14 - x**10 + x**8 - x**6 + x**2 + 1
>>> R.dup_cyclotomic_p(f)
False
>>> g = x**16 + x**14 - x**10 - x**8 - x**6 + x**2 + 1
>>> R.dup_cyclotomic_p(g)
True
diofant.polys.factortools.dup_zz_cyclotomic_poly(n, K)[source]

Efficiently generate n-th cyclotomic polynomial.

diofant.polys.factortools.dup_zz_cyclotomic_factor(f, K)[source]

Efficiently factor polynomials \(x**n - 1\) and \(x**n + 1\) in \(Z[x]\).

Given a univariate polynomial \(f\) in \(Z[x]\) returns a list of factors of \(f\), provided that \(f\) is in the form \(x**n - 1\) or \(x**n + 1\) for \(n >= 1\). Otherwise returns None.

Factorization is performed using using cyclotomic decomposition of \(f\), which makes this method much faster that any other direct factorization approach (e.g. Zassenhaus’s).

References

[R4040][Weisstein09]
diofant.polys.factortools.dup_zz_factor_sqf(f, K)[source]

Factor square-free (non-primitive) polynomials in \(Z[x]\).

diofant.polys.factortools.dup_zz_factor(f, K)[source]

Factor (non square-free) polynomials in \(Z[x]\).

Given a univariate polynomial \(f\) in \(Z[x]\) computes its complete factorization \(f_1, ..., f_n\) into irreducibles over integers:

f = content(f) f_1**k_1 ... f_n**k_n

The factorization is computed by reducing the input polynomial into a primitive square-free polynomial and factoring it using Zassenhaus algorithm. Trial division is used to recover the multiplicities of factors.

The result is returned as a tuple consisting of:

(content(f), [(f_1, k_1), ..., (f_n, k_n))

References

[R4242][Gathen99]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> R.dup_zz_factor(2*x**4 - 2)
(2, [(x - 1, 1), (x + 1, 1), (x**2 + 1, 1)])

Note that this is a complete factorization over integers, however over Gaussian integers we can factor the last term.

By default, polynomials \(x**n - 1\) and \(x**n + 1\) are factored using cyclotomic decomposition to speedup computations. To disable this behaviour set cyclotomic=False.

diofant.polys.factortools.dmp_zz_wang_non_divisors(E, cs, ct, K)[source]

Wang/EEZ: Compute a set of valid divisors.

diofant.polys.factortools.dmp_zz_wang_test_points(f, T, ct, A, u, K)[source]

Wang/EEZ: Test evaluation points for suitability.

diofant.polys.factortools.dmp_zz_wang_lead_coeffs(f, T, cs, E, H, A, u, K)[source]

Wang/EEZ: Compute correct leading coefficients.

diofant.polys.factortools.dmp_zz_diophantine(F, c, A, d, p, u, K)[source]

Wang/EEZ: Solve multivariate Diophantine equations.

diofant.polys.factortools.dmp_zz_wang_hensel_lifting(f, H, LC, A, p, u, K)[source]

Wang/EEZ: Parallel Hensel lifting algorithm.

diofant.polys.factortools.dmp_zz_wang(f, u, K, mod=None, seed=None)[source]

Factor primitive square-free polynomials in \(Z[X]\).

Given a multivariate polynomial \(f\) in \(Z[x_1,...,x_n]\), which is primitive and square-free in \(x_1\), computes factorization of \(f\) into irreducibles over integers.

The procedure is based on Wang’s Enhanced Extended Zassenhaus algorithm. The algorithm works by viewing \(f\) as a univariate polynomial in \(Z[x_2,...,x_n][x_1]\), for which an evaluation mapping is computed:

x_2 -> a_2, ..., x_n -> a_n

where \(a_i\), for \(i = 2, ..., n\), are carefully chosen integers. The mapping is used to transform \(f\) into a univariate polynomial in \(Z[x_1]\), which can be factored efficiently using Zassenhaus algorithm. The last step is to lift univariate factors to obtain true multivariate factors. For this purpose a parallel Hensel lifting procedure is used.

The parameter seed is passed to _randint and can be used to seed randint (when an integer) or (for testing purposes) can be a sequence of numbers.

References

[R4445][Wang78]
[R4545][Geddes92]
diofant.polys.factortools.dmp_zz_factor(f, u, K)[source]

Factor (non square-free) polynomials in \(Z[X]\).

Given a multivariate polynomial \(f\) in \(Z[x]\) computes its complete factorization \(f_1, ..., f_n\) into irreducibles over integers:

f = content(f) f_1**k_1 ... f_n**k_n

The factorization is computed by reducing the input polynomial into a primitive square-free polynomial and factoring it using Enhanced Extended Zassenhaus (EEZ) algorithm. Trial division is used to recover the multiplicities of factors.

The result is returned as a tuple consisting of:

(content(f), [(f_1, k_1), ..., (f_n, k_n))

References

[R4848][Gathen99]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x y", ZZ)
>>> R.dmp_zz_factor(2*x**2 - 2*y**2)
(2, [(x - y, 1), (x + y, 1)])
diofant.polys.factortools.dmp_ext_factor(f, u, K)[source]

Factor multivariate polynomials over algebraic number fields.

diofant.polys.factortools.dup_gf_factor(f, K)[source]

Factor univariate polynomials over finite fields.

diofant.polys.factortools.dmp_factor_list(f, u, K0)[source]

Factor polynomials into irreducibles in \(K[X]\).

diofant.polys.factortools.dmp_factor_list_include(f, u, K)[source]

Factor polynomials into irreducibles in \(K[X]\).

diofant.polys.factortools.dmp_irreducible_p(f, u, K)[source]

Returns True if f has no factors over its domain.

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.

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 or setup(), where method can be either buchberger or f5b.

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

Notes

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

References

[R5054][Bose03]
[R5154][Giovini91]
[R5254][Ajwa95]
[R5354][Cox97]
[R5454](1, 2) [BeckerWeispfenning93], page 232
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

[R6061]Yao Sun, Dingkang Wang: “A New Proof for the Correctness of F5 (F5-Like) Algorithm”, https://arxiv.org/abs/1004.0084 (specifically v4).
[R6161][BeckerWeispfenning93], pp. 203, 216.
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

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

Compute reduced Gröbner basis [R6464].

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

References

[R6464](1, 2) [BeckerWeispfenning93], page 216.
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.fglmtools.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

[R6666]J.C. Faugère, P. Gianni, D. Lazard, T. Mora (1994). Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering.

Gröbner basis algorithms for modules are also provided:

diofant.polys.distributedmodules.sdm_spoly(f, g, O, K, phantom=None)[source]

Compute the generalized s-polynomial of f and g.

The ground field is assumed to be K, and monomials ordered according to O.

This is invalid if either of f or g is zero.

If the leading terms of \(f\) and \(g\) involve different basis elements of \(F\), their s-poly is defined to be zero. Otherwise it is a certain linear combination of \(f\) and \(g\) in which the leading terms cancel. See [SCA, defn 2.3.6] for details.

If phantom is not None, it should be a pair of module elements on which to perform the same operation(s) as on f and g. The in this case both results are returned.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys import lex
>>> f = [((2, 1, 1), QQ(1)), ((1, 0, 1), QQ(1))]
>>> g = [((2, 3, 0), QQ(1))]
>>> h = [((1, 2, 3), QQ(1))]
>>> sdm_spoly(f, h, lex, QQ)
[]
>>> sdm_spoly(f, g, lex, QQ)
[((1, 2, 1), 1)]
diofant.polys.distributedmodules.sdm_ecart(f)[source]

Compute the ecart of f.

This is defined to be the difference of the total degree of \(f\) and the total degree of the leading monomial of \(f\) [SCA, defn 2.3.7].

Invalid if f is zero.

Examples

>>> sdm_ecart([((1, 2, 3), 1), ((1, 0, 1), 1)])
0
>>> sdm_ecart([((2, 2, 1), 1), ((1, 5, 1), 1)])
3
diofant.polys.distributedmodules.sdm_nf_mora(f, G, O, K, phantom=None)[source]

Compute a weak normal form of f with respect to G and order O.

The ground field is assumed to be K, and monomials ordered according to O.

Weak normal forms are defined in [SCA, defn 2.3.3]. They are not unique. This function deterministically computes a weak normal form, depending on the order of \(G\).

The most important property of a weak normal form is the following: if \(R\) is the ring associated with the monomial ordering (if the ordering is global, we just have \(R = K[x_1, \ldots, x_n]\), otherwise it is a certain localization thereof), \(I\) any ideal of \(R\) and \(G\) a standard basis for \(I\), then for any \(f \in R\), we have \(f \in I\) if and only if \(NF(f | G) = 0\).

This is the generalized Mora algorithm for computing weak normal forms with respect to arbitrary monomial orders [SCA, algorithm 2.3.9].

If phantom is not None, it should be a pair of “phantom” arguments on which to perform the same computations as on f, G, both results are then returned.

diofant.polys.distributedmodules.sdm_groebner(G, NF, O, K, extended=False)[source]

Compute a minimal standard basis of G with respect to order O.

The algorithm uses a normal form NF, for example sdm_nf_mora. The ground field is assumed to be K, and monomials ordered according to O.

Let \(N\) denote the submodule generated by elements of \(G\). A standard basis for \(N\) is a subset \(S\) of \(N\), such that \(in(S) = in(N)\), where for any subset \(X\) of \(F\), \(in(X)\) denotes the submodule generated by the initial forms of elements of \(X\). [SCA, defn 2.3.2]

A standard basis is called minimal if no subset of it is a standard basis.

One may show that standard bases are always generating sets.

Minimal standard bases are not unique. This algorithm computes a deterministic result, depending on the particular order of \(G\).

If extended=True, also compute the transition matrix from the initial generators to the groebner basis. That is, return a list of coefficient vectors, expressing the elements of the groebner basis in terms of the elements of G.

This functions implements the “sugar” strategy, see

Giovini et al: “One sugar cube, please” OR Selection strategies in Buchberger algorithm.

Exceptions

These are exceptions defined by the polynomials module.

TODO sort and explain

class diofant.polys.polyerrors.BasePolynomialError[source]

Base class for polynomial related exceptions.

class diofant.polys.polyerrors.ExactQuotientFailed(f, g, dom=None)[source]
class diofant.polys.polyerrors.OperationNotSupported(poly, func)[source]
class diofant.polys.polyerrors.HeuristicGCDFailed[source]
class diofant.polys.polyerrors.HomomorphismFailed[source]
class diofant.polys.polyerrors.IsomorphismFailed[source]
class diofant.polys.polyerrors.ExtraneousFactors[source]
class diofant.polys.polyerrors.EvaluationFailed[source]
class diofant.polys.polyerrors.RefinementFailed[source]
class diofant.polys.polyerrors.CoercionFailed[source]
class diofant.polys.polyerrors.NotInvertible[source]
class diofant.polys.polyerrors.NotReversible[source]
class diofant.polys.polyerrors.NotAlgebraic[source]
class diofant.polys.polyerrors.DomainError[source]
class diofant.polys.polyerrors.PolynomialError[source]
class diofant.polys.polyerrors.UnificationFailed[source]
class diofant.polys.polyerrors.GeneratorsNeeded[source]
class diofant.polys.polyerrors.ComputationFailed(func, nargs, exc)[source]
class diofant.polys.polyerrors.GeneratorsError[source]
class diofant.polys.polyerrors.UnivariatePolynomialError[source]
class diofant.polys.polyerrors.MultivariatePolynomialError[source]
class diofant.polys.polyerrors.PolificationFailed(opt, origs, exprs, seq=False)[source]
class diofant.polys.polyerrors.OptionError[source]
class diofant.polys.polyerrors.FlagError[source]

Reference

Modular GCD

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

Computes the GCD of two polynomials in \(\mathbb{Z}[x]\) using a modular algorithm.

The algorithm computes the GCD of two univariate integer polynomials \(f\) and \(g\) by computing the GCD in \(\mathbb{Z}_p[x]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem. Trial division is only made for candidates which are very likely the desired GCD.

Parameters:

f : PolyElement

univariate integer polynomial

g : PolyElement

univariate integer polynomial

Returns:

h : PolyElement

GCD of the polynomials \(f\) and \(g\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac{f}{h}\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac{g}{h}\)

References

[R6868][Monagan00]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x = ring("x", ZZ)
>>> f = x**5 - 1
>>> g = x - 1
>>> h, cff, cfg = modgcd_univariate(f, g)
>>> h, cff, cfg
(x - 1, x**4 + x**3 + x**2 + x + 1, 1)
>>> cff * h == f
True
>>> cfg * h == g
True
>>> f = 6*x**2 - 6
>>> g = 2*x**2 + 4*x + 2
>>> h, cff, cfg = modgcd_univariate(f, g)
>>> h, cff, cfg
(2*x + 2, 3*x - 3, x + 1)
>>> cff * h == f
True
>>> cfg * h == g
True
diofant.polys.modulargcd.modgcd_bivariate(f, g)[source]

Computes the GCD of two polynomials in \(\mathbb{Z}[x, y]\) using a modular algorithm.

The algorithm computes the GCD of two bivariate integer polynomials \(f\) and \(g\) by calculating the GCD in \(\mathbb{Z}_p[x, y]\) for suitable primes \(p\) and then reconstructing the coefficients with the Chinese Remainder Theorem. To compute the bivariate GCD over \(\mathbb{Z}_p\), the polynomials \(f \; \mathrm{mod} \, p\) and \(g \; \mathrm{mod} \, p\) are evaluated at \(y = a\) for certain \(a \in \mathbb{Z}_p\) and then their univariate GCD in \(\mathbb{Z}_p[x]\) is computed. Interpolating those yields the bivariate GCD in \(\mathbb{Z}_p[x, y]\). To verify the result in \(\mathbb{Z}[x, y]\), trial division is done, but only for candidates which are very likely the desired GCD.

Parameters:

f : PolyElement

bivariate integer polynomial

g : PolyElement

bivariate integer polynomial

Returns:

h : PolyElement

GCD of the polynomials \(f\) and \(g\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac{f}{h}\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac{g}{h}\)

References

[R7070][Monagan00]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x, y", ZZ)
>>> f = x**2 - y**2
>>> g = x**2 + 2*x*y + y**2
>>> h, cff, cfg = modgcd_bivariate(f, g)
>>> h, cff, cfg
(x + y, x - y, x + y)
>>> cff * h == f
True
>>> cfg * h == g
True
>>> f = x**2*y - x**2 - 4*y + 4
>>> g = x + 2
>>> h, cff, cfg = modgcd_bivariate(f, g)
>>> h, cff, cfg
(x + 2, x*y - x - 2*y + 2, 1)
>>> cff * h == f
True
>>> cfg * h == g
True
diofant.polys.modulargcd.modgcd_multivariate(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_multivariate_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\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac{f}{h}\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac{g}{h}\)

References

[R7273][Monagan00]
[R7373][Brown71]

Examples

>>> from diofant.domains import ZZ
>>> from diofant.polys import ring
>>> R, x, y = ring("x, y", ZZ)
>>> f = x**2 - y**2
>>> g = x**2 + 2*x*y + y**2
>>> h, cff, cfg = modgcd_multivariate(f, g)
>>> h, cff, cfg
(x + y, x - y, x + y)
>>> cff * h == f
True
>>> cfg * h == g
True
>>> R, x, y, z = ring("x, y, z", ZZ)
>>> f = x*z**2 - y*z**2
>>> g = x**2*z + z
>>> h, cff, cfg = modgcd_multivariate(f, g)
>>> h, cff, cfg
(z, x*z - y*z, x**2 + 1)
>>> cff * h == f
True
>>> cfg * h == g
True
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\)

cff : PolyElement

cofactor of \(f\), i.e. \(\frac f h\)

cfg : PolyElement

cofactor of \(g\), i.e. \(\frac g h\)

References

[R7676][Hoeij04]

Examples

>>> from diofant.domains import AlgebraicField, QQ
>>> from diofant.polys import ring
>>> from diofant import sqrt
>>> A = AlgebraicField(QQ, sqrt(2))
>>> R, x = ring('x', A)
>>> f = x**2 - 2
>>> g = x + sqrt(2)
>>> h, cff, cfg = func_field_modgcd(f, g)
>>> h == x + sqrt(2)
True
>>> cff * h == f
True
>>> cfg * h == g
True
>>> R, x, y = ring('x, y', A)
>>> f = x**2 + 2*sqrt(2)*x*y + 2*y**2
>>> g = x + sqrt(2)*y
>>> h, cff, cfg = func_field_modgcd(f, g)
>>> h == x + sqrt(2)*y
True
>>> cff * h == f
True
>>> cfg * h == g
True
>>> f = x + sqrt(2)*y
>>> g = x + y
>>> h, cff, cfg = func_field_modgcd(f, g)
>>> h == R.one
True
>>> cff * h == f
True
>>> cfg * h == g
True
diofant.polys.modulargcd._modgcd_multivariate_p(f, g, p, degbound, contbound)[source]

Compute the GCD of two polynomials in \(\mathbb{Z}_p[x0, \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 integer polynomial with coefficients in \(\mathbb{Z}_p\)

g : PolyElement

multivariate integer polynomial with coefficients in \(\mathbb{Z}_p\)

p : Integer

prime number, modulus of \(f\) and \(g\)

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

[R7879][Monagan00]
[R7979][Brown71]
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

[R8282][Hoeij02]
diofant.polys.modulargcd.integer_rational_reconstruction(c, m, domain)[source]

Reconstruct a rational number \(\frac a b\) from

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

where \(c\) and \(m\) are integers.

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

Parameters:

c : Integer

\(c = \frac a b \; \mathrm{mod} \, m\)

m : Integer

modulus, not necessarily prime

domain : IntegerRing

\(a, b, c\) are elements of domain

Returns:

frac : Rational

either \(\frac a b\) in \(\mathbb Q\) or None

References

[R8484][Wang81]

Manipulation of power series

Functions in this module carry the prefix rs_, standing for “ring series”. They manipulate finite power series in the sparse representation provided by polys.ring.ring.

diofant.polys.ring_series.rs_trunc(p1, x, prec)[source]

truncate the series in the x variable with precision prec, that is modulo O(x**prec)

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p = x**10 + x**5 + x + 1
>>> rs_trunc(p, x, 12)
x**10 + x**5 + x + 1
>>> rs_trunc(p, x, 10)
x**5 + x + 1
diofant.polys.ring_series.rs_mul(p1, p2, x, prec)[source]

product of series modulo O(x**prec)

x is the series variable or its position in the generators.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p1 = x**2 + 2*x + 1
>>> p2 = x + 1
>>> rs_mul(p1, p2, x, 3)
3*x**2 + 3*x + 1
diofant.polys.ring_series.rs_square(p1, x, prec)[source]

square modulo O(x**prec)

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p = x**2 + 2*x + 1
>>> rs_square(p, x, 3)
6*x**2 + 4*x + 1
diofant.polys.ring_series.rs_pow(p1, n, x, prec)[source]

return p1**n modulo O(x**prec)

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p = x + 1
>>> rs_pow(p, 4, x, 3)
6*x**2 + 4*x + 1
diofant.polys.ring_series.rs_series_inversion(p, x, prec)[source]

multivariate series inversion 1/p modulo O(x**prec)

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x, y = ring('x, y', QQ)
>>> rs_series_inversion(1 + x*y**2, x, 4)
-x**3*y**6 + x**2*y**4 - x*y**2 + 1
>>> rs_series_inversion(1 + x*y**2, y, 4)
-x*y**2 + 1
diofant.polys.ring_series.rs_series_from_list(p, c, x, prec, concur=1)[source]

series sum c[n]*p**n modulo O(x**prec)

reduce the number of multiplication summing concurrently ax = [1, p, p**2, .., p**(J - 1)] s = sum(c[i]*ax[i] for i in range(r, (r + 1)*J))*p**((K - 1)*J) with K >= (n + 1)/J

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p = x**2 + x + 1
>>> c = [1, 2, 3]
>>> rs_series_from_list(p, c, x, 4)
6*x**3 + 11*x**2 + 8*x + 6
>>> rs_trunc(1 + 2*p + 3*p**2, x, 4)
6*x**3 + 11*x**2 + 8*x + 6
>>> pc = R.from_list(list(reversed(c)))
>>> rs_trunc(pc.compose(x, p), x, 4)
6*x**3 + 11*x**2 + 8*x + 6
diofant.polys.ring_series.rs_integrate(self, x)[source]

integrate p with respect to x

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x, y = ring('x, y', QQ)
>>> p = x + x**2*y**3
>>> rs_integrate(p, x)
1/3*x**3*y**3 + 1/2*x**2
diofant.polys.ring_series.rs_log(p, x, prec)[source]

logarithm of p modulo O(x**prec)

Notes

truncation of integral dx p**-1*d p/dx is used.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> rs_log(1 + x, x, 8)
1/7*x**7 - 1/6*x**6 + 1/5*x**5 - 1/4*x**4 + 1/3*x**3 - 1/2*x**2 + x
diofant.polys.ring_series.rs_exp(p, x, prec)[source]

exponentiation of a series modulo O(x**prec)

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> rs_exp(x**2, x, 7)
1/6*x**6 + 1/2*x**4 + x**2 + 1
diofant.polys.ring_series.rs_newton(p, x, prec)[source]

compute the truncated Newton sum of the polynomial p

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p = x**2 - 2
>>> rs_newton(p, x, 5)
8*x**4 + 4*x**2 + 2
diofant.polys.ring_series.rs_hadamard_exp(p1, inverse=False)[source]

return sum f_i/i!*x**i from sum f_i*x**i, where x is the first variable.

If invers=True return sum f_i*i!*x**i

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> p = 1 + x + x**2 + x**3
>>> rs_hadamard_exp(p)
1/6*x**3 + 1/2*x**2 + x + 1
diofant.polys.ring_series.rs_compose_add(p1, p2)[source]

compute the composed sum prod(p2(x - beta) for beta root of p1)

References

[R8686]A. Bostan, P. Flajolet, B. Salvy and E. Schost “Fast Computation with Two Algebraic Numbers”, (2002) Research Report 4579, Institut National de Recherche en Informatique et en Automatique.

Examples

>>> from diofant.domains import QQ
>>> from diofant.polys.rings import ring
>>> R, x = ring('x', QQ)
>>> f = x**2 - 2
>>> g = x**2 - 3
>>> rs_compose_add(f, g)
x**4 - 10*x**2 + 1

Undocumented

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

class diofant.polys.polyoptions.Order[source]

order option to polynomial manipulation functions.

class diofant.polys.polyoptions.Options(gens, args, flags=None, strict=False)[source]

Options manager for polynomial manipulation module.

Examples

>>> from diofant.domains import ZZ
>>> from diofant.abc import x, y, z
>>> Options((x, y, z), {'domain': 'ZZ'})
{'auto': False, 'domain': ZZ, 'gens': (x, y, z)}
>>> build_options((x, y, z), {'domain': 'ZZ'})
{'auto': False, 'domain': ZZ, 'gens': (x, y, z)}

Options

  • Expand — boolean option
  • Gens — option
  • Wrt — option
  • Sort — option
  • Order — option
  • Field — boolean option
  • Greedy — boolean option
  • Domain — option
  • Split — boolean option
  • Gaussian — boolean option
  • Extension — option
  • Modulus — option
  • Symmetric — boolean option
  • Strict — boolean option

Flags

  • Auto — boolean flag
  • Frac — boolean flag
  • Formal — boolean flag
  • Polys — boolean flag
  • Include — boolean flag
  • All — boolean flag
  • Gen — flag
diofant.polys.polyconfig.setup(key, value=None)[source]

Assign a value to (or reset) a configuration item.