Internals of the Polynomial Manipulation Module¶

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

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

Manipulation of 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:

Basic tools for dense recursive polynomials in K[x] or K[X].

diofant.polys.densebasic.dmp_LC(f, K)[source]

Return leading coefficient of f.

Examples

>>> R, x = ring('x', ZZ)

>>> R.dmp_LC(x**2 + 2*x + 3)
1

diofant.polys.densebasic.dmp_TC(f, K)[source]

Return trailing coefficient of f.

Examples

>>> R, x = ring('x', ZZ)

>>> R.dmp_TC(x**2 + 2*x + 3)
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

>>> h = lambda x, y, z: 2*x + y - z

>>> dmp_apply_pairs([[ZZ(1)], [ZZ(2), ZZ(3)]],
...                 [[ZZ(3)], [ZZ(2), ZZ(1)]], h, [ZZ(1)], 1, ZZ)
[[4], [5, 6]]

diofant.polys.densebasic.dmp_convert(f, u, K0, K1)[source]

Convert the ground domain of f from K0 to K1.

Examples

>>> R, x = ring("x", ZZ)

>>> dmp_convert([[R(1)], [R(2)]], 1, R, ZZ)
[[1], [2]]
>>> dmp_convert([[ZZ(1)], [ZZ(2)]], 1, ZZ, R)
[[1], [2]]

diofant.polys.densebasic.dmp_deflate(polys, u, K)[source]

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

Examples

>>> f = [[ZZ(1), ZZ(0), ZZ(0), ZZ(2)], [], [ZZ(3), ZZ(0), ZZ(0), ZZ(4)]]
>>> g = [[ZZ(1), ZZ(0), ZZ(2)], [], [ZZ(3), ZZ(0), ZZ(4)]]

>>> dmp_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_degree_in(f, j, u)[source]

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

Examples

>>> R, x, y = ring('x y', ZZ)

>>> R.dmp_degree_in(2*x + y**2 + 2*y + 3, 1)
2

diofant.polys.densebasic.dmp_degree_list(f, u)[source]

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

Examples

>>> R, x, y = ring('x y', ZZ)

>>> R.dmp_degree_list(x + y**2 + 2*y + 3)
(1, 2)

diofant.polys.densebasic.dmp_eject(f, u, K, front=False)[source]

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

Examples

>>> dmp_eject([[[ZZ(1)]], [[ZZ(1)], [ZZ(2)]]], 2, ZZ.poly_ring('x', 'y'))
[1, x + 2]

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

>>> dmp_exclude([[[ZZ(1)]], [[ZZ(1)], [ZZ(2)]]], 2, ZZ)
([2], [[1], [1, 2]], 1)

diofant.polys.densebasic.dmp_from_dict(f, u, K)[source]

Create a K[X] polynomial from a dict.

Examples

>>> dmp_from_dict({(0, 0): ZZ(3), (0, 1): ZZ(2), (2, 1): ZZ(1)}, 1, ZZ)
[[1, 0], [], [2, 3]]

diofant.polys.densebasic.dmp_ground(c, u)[source]

Return a multivariate constant.

Examples

>>> dmp_ground(ZZ(3), 5)
[[[[[[3]]]]]]
>>> dmp_ground(ZZ(1), -1)
1

diofant.polys.densebasic.dmp_ground_LC(f, u, K)[source]

Examples

>>> R, x, y, z = ring('x y z', ZZ)

>>> R.dmp_ground_LC(y + 2*z + 3)
1

diofant.polys.densebasic.dmp_ground_TC(f, u, K)[source]

Return the ground trailing coefficient.

Examples

>>> R, x, y, z = ring('x y z', ZZ)

>>> R.dmp_ground_TC(y + 2*z + 3)
3

diofant.polys.densebasic.dmp_ground_p(f, c, u)[source]

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

Examples

>>> dmp_ground_p([[[ZZ(3)]]], 3, 2)
True
>>> dmp_ground_p([[[ZZ(4)]]], None, 2)
True

diofant.polys.densebasic.dmp_include(f, J, u, K)[source]

Include useless levels in f.

Examples

>>> dmp_include([[ZZ(1)], [ZZ(1), ZZ(2)]], [2], 1, ZZ)
[[[1]], [[1], [2]]]

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

>>> dmp_inflate([[ZZ(1), ZZ(2)], [ZZ(3), ZZ(4)]], (2, 3), 1, ZZ)
[[1, 0, 0, 2], [], [3, 0, 0, 4]]

diofant.polys.densebasic.dmp_inject(f, u, K, front=False)[source]

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

Examples

>>> R, x, y = ring("x y", ZZ)

>>> dmp_inject([R(1), x + 2], 0, R)
([[[1]], [[1], [2]]], 2)
>>> dmp_inject([R(1), x + 2], 0, R, front=True)
([[[1]], [[1, 2]]], 2)

diofant.polys.densebasic.dmp_nest(f, l, K)[source]

Return a multivariate value nested l-levels.

Examples

>>> dmp_nest([[ZZ(1)]], 2, ZZ)
[[[[1]]]]

diofant.polys.densebasic.dmp_normal(f, u, K)[source]

Normalize a multivariate polynomial in the given domain.

Examples

>>> dmp_normal([[], [0, 1.5, 2]], 1, ZZ)
[[1, 2]]

diofant.polys.densebasic.dmp_one(u, K)[source]

Return a multivariate one over K.

Examples

>>> dmp_one(2, ZZ)
[[[1]]]

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

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

Examples

>>> dmp_one_p([[[ZZ(1)]]], 2, ZZ)
True

diofant.polys.densebasic.dmp_permute(f, P, u, K)[source]

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

Examples

>>> dmp_permute([[[ZZ(2)], [ZZ(1), ZZ(0)]], []], [1, 0, 2], 2, ZZ)
[[[2], []], [[1, 0], []]]

diofant.polys.densebasic.dmp_raise(f, l, u, K)[source]

Return a multivariate polynomial raised l-levels.

Examples

>>> dmp_raise([[], [ZZ(1), ZZ(2)]], 2, 1, ZZ)
[[[[]]], [[[1]], [[2]]]]

diofant.polys.densebasic.dmp_slice_in(f, m, n, j, u, K)[source]

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

diofant.polys.densebasic.dmp_strip(f, u)[source]

Remove leading zeros from f in K[X].

Examples

>>> dmp_strip([[], [ZZ(0), ZZ(1), ZZ(2)], [ZZ(1)]], 1)
[[0, 1, 2], [1]]

diofant.polys.densebasic.dmp_swap(f, i, j, u, K)[source]

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

Examples

>>> dmp_swap([[[ZZ(2)], [ZZ(1), ZZ(0)]], []], 0, 1, 2, ZZ)
[[[2], []], [[1, 0], []]]

diofant.polys.densebasic.dmp_terms_gcd(f, u, K)[source]

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

Examples

>>> dmp_terms_gcd([[ZZ(1), ZZ(0)], [ZZ(1), ZZ(0), ZZ(0)], [], []], 1, ZZ)
((2, 1), [[1], [1, 0]])

diofant.polys.densebasic.dmp_to_dict(f, u)[source]

Convert a K[X] polynomial to a dict.

Examples

>>> dmp_to_dict([[ZZ(1), ZZ(0)], [], [ZZ(2), ZZ(3)]], 1)
{(0, 0): 3, (0, 1): 2, (2, 1): 1}

diofant.polys.densebasic.dmp_to_tuple(f, u)[source]

Convert f into a nested tuple.

This is needed for hashing.

Examples

>>> dmp_to_tuple([ZZ(1), ZZ(2), ZZ(3), ZZ(0)], 0)
(1, 2, 3, 0)

>>> dmp_to_tuple([[ZZ(1)], [ZZ(1), ZZ(2)]], 1)
((1,), (1, 2))

diofant.polys.densebasic.dmp_zero(u)[source]

Return a multivariate zero.

Examples

>>> dmp_zero(4)
[[[[[]]]]]

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([[[[[ZZ(1)]]]]], 4)
False

diofant.polys.densebasic.dmp_zeros(n, u, K)[source]

Return a list of multivariate zeros.

Examples

>>> dmp_zeros(3, 2, ZZ)
[[[[]]], [[[]]], [[[]]]]
>>> dmp_zeros(3, -1, ZZ)
[0, 0, 0]

diofant.polys.densebasic.dup_from_dict(f, K)[source]

Create a K[x] polynomial from a dict.

Examples

>>> dmp_from_dict({(0,): ZZ(7), (2,): ZZ(5), (4,): ZZ(1)}, 0, ZZ)
[1, 0, 5, 0, 7]

diofant.polys.densebasic.dup_inflate(f, m, K)[source]

Map y to x**m in a polynomial in K[x].

Examples

>>> dup_inflate([ZZ(1), ZZ(1), ZZ(1)], 3, ZZ)
[1, 0, 0, 1, 0, 0, 1]

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

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

If percent is a natural number less than 100 then only approximately the given percentage of elements will be non-zero.

Examples

>>> dup_random(3, -10, 10, ZZ) #doctest: +SKIP
[-2, -8, 9, -4]

diofant.polys.densebasic.dup_reverse(f)[source]

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

Examples

>>> dup_reverse([ZZ(1), ZZ(2), ZZ(3), ZZ(0)])
[3, 2, 1]


Arithmetic operations:

Arithmetics for dense recursive polynomials in K[x] or K[X].

diofant.polys.densearith.dmp_abs(f, u, K)[source]

Make all coefficients positive in K[X].

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_abs(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

>>> 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_add_mul(f, g, h, u, K)[source]

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

Examples

>>> 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_add_term(f, c, i, u, K)[source]

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

Examples

>>> 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_div(f, g, u, K)[source]

Polynomial division with remainder in K[X].

Examples

>>> 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_expand(polys, u, K)[source]

Multiply together several polynomials in K[X].

Examples

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

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

Exact quotient by a constant in K[X].

Examples

>>> 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.dmp_l1_norm(f, u, K)[source]

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

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_l1_norm(2*x*y - x - 3)
6

diofant.polys.densearith.dmp_max_norm(f, u, K)[source]

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

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_max_norm(2*x*y - x - 3)
3

diofant.polys.densearith.dmp_mul(f, g, u, K)[source]

Multiply dense polynomials in K[X].

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_mul(x*y + 1, x)
x**2*y + x

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

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

Examples

>>> 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_mul_term(f, c, i, u, K)[source]

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

Examples

>>> 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_neg(f, u, K)[source]

Negate a polynomial in K[X].

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_neg(x**2*y - x)
-x**2*y + x

diofant.polys.densearith.dmp_pow(f, n, u, K)[source]

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

Examples

>>> 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_quo(f, g, u, K)[source]

Return exact polynomial quotient in K[X].

Examples

>>> 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_quo_ground(f, c, u, K)[source]

Quotient by a constant in K[X].

Examples

>>> 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_rem(f, g, u, K)[source]

Return polynomial remainder in K[X].

Examples

>>> 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_sqr(f, u, K)[source]

Square dense polynomials in K[X].

Examples

>>> 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_sub(f, g, u, K)[source]

Subtract dense polynomials in K[X].

Examples

>>> 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_sub_mul(f, g, h, u, K)[source]

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

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_sub_mul(x**2 + y, x, x + 2)
-2*x + y

diofant.polys.densearith.dup_add(f, g, K)[source]

Add dense polynomials in K[x].

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_add(x**2 - 1, x - 2)
x**2 + x - 3

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

Add c*x**i to f in K[x].

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_add_term(x**2 - 1, ZZ(2), 4)
2*x**4 + x**2 - 1

diofant.polys.densearith.dup_lshift(f, n, K)[source]

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

Examples

>>> R, x = ring("x", ZZ)

>>> R.dup_lshift(x**2 + 1, 2)
x**4 + x**2

diofant.polys.densearith.dup_mul(f, g, K)[source]

Multiply dense polynomials in K[x].

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_mul(x - 2, x + 2)
x**2 - 4

diofant.polys.densearith.dup_mul_karatsuba(f, g, K)[source]

Multiply dense polynomials in K[x] using Karatsuba’s algorithm.

References

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

Multiply f by c*x**i in K[x].

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_mul_term(x**2 - 1, ZZ(3), 2)
3*x**4 - 3*x**2

diofant.polys.densearith.dup_rshift(f, n, K)[source]

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

Examples

>>> 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.dup_sqr(f, K)[source]

Square dense polynomials in K[x].

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_sqr(x**2 + 1)
x**4 + 2*x**2 + 1

diofant.polys.densearith.dup_sub(f, g, K)[source]

Subtract dense polynomials in K[x].

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_sub(x**2 - 1, x - 2)
x**2 - x + 1


Further tools:

Advanced tools for dense recursive polynomials in K[x] or K[X].

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

>>> 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_compose(f, g, u, K)[source]

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

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_compose(x*y + 2*x + y, y)
y**2 + 3*y

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

>>> 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_diff_in(f, m, j, u, K)[source]

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

Examples

>>> 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_in(f, a, j, u, K)[source]

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

Examples

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

>>> 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_ground_content(f, u, K)[source]

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

Examples

>>> 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.dmp_ground_monic(f, u, K)[source]

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

Examples

>>> 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.dmp_ground_primitive(f, u, K)[source]

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

Examples

>>> 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.dmp_ground_trunc(f, p, u, K)[source]

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

Examples

>>> 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_decompose(f, K)[source]

Compute functional decomposition of f in K[x].

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

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


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

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

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

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

3. T_n o T_m = T_m o T_n

where T_n and T_m are Chebyshev polynomials.

Examples

>>> R, x = ring("x", ZZ)

>>> R.dup_decompose(x**4 - 2*x**3 + x**2)
[x**2, x**2 - x]


References

diofant.polys.densetools.dup_mirror(f, K)[source]

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

Examples

>>> 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_real_imag(f, K)[source]

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

Examples

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

>>> R, x, y = ring("x y", QQ.algebraic_field(I))

>>> R.dup_real_imag(x**2 + I*x - 1)
(x**2 - y**2 - y - 1, 2*x*y + x)

diofant.polys.densetools.dup_scale(f, a, K)[source]

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

Examples

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

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

>>> 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.dup_trunc(f, p, K)[source]

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

Examples

>>> R, x = ring("x", ZZ)

>>> R.dmp_ground_trunc(2*x**3 + 3*x**2 + 5*x + 7, ZZ(3))
-x**3 - x + 1


Real and complex root isolation and refinement algorithms.

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

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

as_tuple()[source]

Return tuple representation of complex isolating interval.

property ax

Return x coordinate of south-western corner.

property ay

Return y coordinate of south-western corner.

property bx

Return x coordinate of north-eastern corner.

property by

Return y coordinate of north-eastern corner.

property center

Return the center of the complex isolating interval.

conjugate()[source]

Return conjugated isolating interval.

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

Return True if two isolation intervals are disjoint.

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

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

refine(vertical=False)[source]

Perform one step of complex root refinement algorithm.

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

A fully qualified representation of a real isolation interval.

property a

Return the position of the left end.

as_tuple()[source]

Return tuple representation of real isolating interval.

property b

Return the position of the right end.

property center

Return the center of the real isolating interval.

is_disjoint(other)[source]

Return True if two isolation intervals are disjoint.

refine()[source]

Perform one step of real root refinement algorithm.

diofant.polys.rootisolation.dup_count_complex_roots(f, K, inf=None, sup=None, exclude=None)[source]

Count all roots in [u + v*I, s + t*I] rectangle using Collins-Krandick algorithm.

diofant.polys.rootisolation.dup_count_real_roots(f, K, inf=None, sup=None)[source]

Returns the number of distinct real roots of f in [inf, sup].

diofant.polys.rootisolation.dup_inner_isolate_negative_roots(f, K, inf=None, sup=None, eps=None, mobius=False)[source]

Iteratively compute disjoint negative root isolation intervals.

diofant.polys.rootisolation.dup_inner_isolate_positive_roots(f, K, eps=None, inf=None, sup=None, mobius=False)[source]

Iteratively compute disjoint positive root isolation intervals.

diofant.polys.rootisolation.dup_inner_isolate_real_roots(f, K, eps=None)[source]

Internal function for isolation positive roots up to given precision.

diofant.polys.rootisolation.dup_inner_refine_real_root(f, M, K, eps=None, steps=None, disjoint=None, mobius=False)[source]

Refine a positive root of $$f$$ given a Mobius transform or an interval.

diofant.polys.rootisolation.dup_isolate_all_roots(f, K, eps=None, inf=None, sup=None)[source]

Isolate real and complex roots of a non-square-free polynomial f.

diofant.polys.rootisolation.dup_isolate_all_roots_sqf(f, K, eps=None, inf=None, sup=None, blackbox=False)[source]

Isolate real and complex roots of a square-free polynomial f.

diofant.polys.rootisolation.dup_isolate_complex_roots_sqf(f, K, eps=None, inf=None, sup=None, blackbox=False)[source]

Isolate complex roots of a square-free polynomial using Collins-Krandick algorithm.

diofant.polys.rootisolation.dup_isolate_real_roots(f, K, eps=None, inf=None, sup=None)[source]

Isolate real roots.

Notes

Implemented algorithms use Vincent-Akritas-Strzebonski (VAS) continued fractions approach [SA05], [ASV08].

diofant.polys.rootisolation.dup_isolate_real_roots_list(polys, K, eps=None, inf=None, sup=None, strict=False, basis=False)[source]

Isolate real roots of a list of polynomials.

diofant.polys.rootisolation.dup_isolate_real_roots_sqf(f, K, eps=None, inf=None, sup=None, blackbox=False)[source]

Isolate real roots of a square-free polynomial.

diofant.polys.rootisolation.dup_outer_refine_real_root(f, s, t, K, eps=None, steps=None, disjoint=None)[source]

Refine a positive root of $$f$$ given an interval $$(s, t)$$.

diofant.polys.rootisolation.dup_refine_real_root(f, s, t, K, eps=None, steps=None, disjoint=None)[source]

Refine real root’s approximating interval to the given precision.

diofant.polys.rootisolation.dup_root_upper_bound(f, K)[source]

Compute the LMQ upper bound for the positive roots of $$f$$.

LMQ (Local Max Quadratic) bound was developed by Akritas-Strzebonski-Vigklas [Akr09].

diofant.polys.rootisolation.dup_sign_variations(f, K)[source]

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

Examples

>>> R, x = ring("x", ZZ)

>>> R.dup_sign_variations(x**4 - x**2 - x + 1)
2

diofant.polys.rootisolation.dup_step_refine_real_root(f, M, K)[source]

One step of positive real root refinement algorithm.

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 (see e.g. [DST88]) f_0(x), ..., f_n(x) defined by:

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


Examples

>>> 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]


Square-free decomposition algorithms and related tools.

diofant.polys.sqfreetools.dmp_gf_sqf_list(f, u, K)[source]

Compute square-free decomposition of 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.

Examples

>>> R, x = ring('x', FF(11))
>>> f = x**11 + 1


Note that:

>>> f.diff()
0 mod 11


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

>>> R.dmp_sqf_list(f)
(1 mod 11, [(x + 1 mod 11, 11)])


References

diofant.polys.sqfreetools.dmp_rr_yun0_sqf_list(f, u, K)[source]

Compute square-free decomposition of f in zero-characteristic ring K.

References

diofant.polys.sqfreetools.dmp_sqf_list(f, u, K)[source]

Return square-free decomposition of a polynomial in K[X].

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_sqf_list(x**5 + 2*x**4*y + x**3*y**2)
(1, [(x + y, 2), (x, 3)])

diofant.polys.sqfreetools.dmp_sqf_norm(f, u, K)[source]

Square-free norm of f in K[X], useful over algebraic domains.

Returns s, f, r, such that g(x) = f(x-sa) and r(x) = Norm(g(x)) is a square-free polynomial over K, where a is the algebraic extension of K.

Examples

>>> K = QQ.algebraic_field(I)
>>> R, x, y = ring("x y", K)

>>> R.dmp_sqf_norm(x*y + y**2)
(1, x*y - I*x + y**2 - 3*I*y - 2,
x**2*y**2 + x**2 + 2*x*y**3 + 2*x*y + y**4 + 5*y**2 + 4)

diofant.polys.sqfreetools.dmp_sqf_p(f, u, K)[source]

Return True if f is a square-free polynomial in K[X].

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_sqf_p(R(0))
True
>>> R.dmp_sqf_p((x + y)**2)
False
>>> R.dmp_sqf_p(x**2 + y**2)
True

diofant.polys.sqfreetools.dmp_sqf_part(f, u, K)[source]

Returns square-free part of a polynomial in K[X].

Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_sqf_part(x**3 + 2*x**2*y + x*y**2)
x**2 + x*y


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.

Dense univariate polynomials with coefficients in Galois fields.

diofant.polys.galoistools.gf_Qbasis(Q, p, K)[source]

Compute a basis of the kernel of Q.

Examples

>>> 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_Qmatrix(f, p, K)[source]

Calculate Berlekamp’s Q matrix.

Examples

>>> 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_add(f, g, p, K)[source]

Add polynomials in GF(p)[x].

Examples

>>> gf_add([3, 2, 4], [2, 2, 2], 5, ZZ)
[4, 1]

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

>>> gf_add_ground([3, 2, 4], 2, 5, ZZ)
[3, 2, 1]

diofant.polys.galoistools.gf_berlekamp(f, p, K)[source]

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

Examples

>>> gf_berlekamp([1, 0, 0, 0, 1], 5, ZZ)
[[1, 0, 2], [1, 0, 3]]

diofant.polys.galoistools.gf_compose_mod(g, h, f, p, K)[source]

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

Examples

>>> gf_compose_mod([3, 2, 4], [2, 2, 2], [4, 3], 5, ZZ)
[4]

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

Examples

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


References

diofant.polys.galoistools.gf_ddf_zassenhaus(f, p, K)[source]

Cantor-Zassenhaus: 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.

Examples

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

>>> gf_ddf_zassenhaus(f, 11, ZZ)
[([1, 0, 0, 0, 0, 10], 1), ([1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1], 2)]


To obtain factorization into irreducibles, use equal degree factorization procedure (EDF) with each of the factors.

References

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.

Examples

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


References

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

Examples

>>> gf_edf_shoup([1, 2837, 2277], 1, 2917, ZZ)
[[1, 852], [1, 1985]]


References

diofant.polys.galoistools.gf_edf_zassenhaus(f, n, p, K)[source]

Cantor-Zassenhaus: Probabilistic Equal Degree Factorization

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

Examples

>>> gf_edf_zassenhaus([1, 1, 1, 1], 1, 5, ZZ)
[[1, 1], [1, 2], [1, 3]]


References

diofant.polys.galoistools.gf_factor_sqf(f, p, K)[source]

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

Returns its complete factorization into irreducibles:

f_1(x) f_2(x) ... f_d(x)


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.

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.

Examples

>>> gf_factor_sqf([3, 2, 4], 5, ZZ)
(3, [[1, 1], [1, 3]])


References

diofant.polys.galoistools.gf_frobenius_map(f, g, b, p, K)[source]

compute gf_pow_mod(f, p, g, p, K) using the Frobenius map

Parameters
• f, g (polynomials in GF(p)[x])

• b (frobenius monomial base)

• p (prime number)

• K (domain)

Examples

>>> f = [2, 1, 0, 1]
>>> g = [1, 0, 2, 1]
>>> p = 5
>>> b = gf_frobenius_monomial_base(g, p, ZZ)
>>> r = gf_frobenius_map(f, g, b, p, ZZ)
>>> gf_frobenius_map(f, g, b, p, ZZ)
[4, 0, 3]

diofant.polys.galoistools.gf_frobenius_monomial_base(g, p, K)[source]

return the list of x**(i*p) mod g in Z_p for i = 0, .., n - 1 where n = dmp_degree_in(g, 0, 0)

Examples

>>> gf_frobenius_monomial_base([1, 0, 2, 1], 5, ZZ)
[[1], [4, 4, 2], [1, 2]]

diofant.polys.galoistools.gf_from_dict(f, p, K)[source]

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

Examples

>>> gf_from_dict({10: 4, 4: 33, 0: -1}, 5, ZZ)
[4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 4]

diofant.polys.galoistools.gf_gcd(f, g, p, K)[source]

Euclidean Algorithm in GF(p)[x].

Examples

>>> gf_gcd([3, 2, 4], [2, 2, 3], 5, ZZ)
[1, 3]

diofant.polys.galoistools.gf_irred_p_ben_or(f, p, K)[source]

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

Examples

>>> gf_irred_p_ben_or([1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4], 5, ZZ)
True
>>> gf_irred_p_ben_or([3, 2, 4], 5, ZZ)
False


References

diofant.polys.galoistools.gf_irred_p_rabin(f, p, K)[source]

Rabin’s polynomial irreducibility test over finite fields.

Examples

>>> gf_irred_p_rabin([1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4], 5, ZZ)
True
>>> gf_irred_p_rabin([3, 2, 4], 5, ZZ)
False

diofant.polys.galoistools.gf_irreducible(n, p, K)[source]

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

Examples

>>> gf_irreducible(10, 5, ZZ) #doctest: +SKIP
[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

>>> gf_irreducible_p([1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4], 5, ZZ)
True
>>> gf_irreducible_p([3, 2, 4], 5, ZZ)
False

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

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

Examples

>>> gf_monic([3, 2, 4], 5, ZZ)
(3, [1, 4, 3])

diofant.polys.galoistools.gf_mul(f, g, p, K)[source]

Multiply polynomials in GF(p)[x].

Examples

>>> gf_mul([3, 2, 4], [2, 2, 2], 5, ZZ)
[1, 0, 3, 2, 3]

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

>>> gf_mul_ground([3, 2, 4], 2, 5, ZZ)
[1, 4, 3]

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.

Examples

>>> gf_pow_mod([3, 2, 4], 3, [1, 1], 5, ZZ)
[]


References

diofant.polys.galoistools.gf_quo(f, g, p, K)[source]

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

Examples

>>> gf_quo([1, 0, 1, 1], [1, 1, 0], 2, ZZ)
[1, 1]
>>> gf_quo([1, 0, 3, 2, 3], [2, 2, 2], 5, ZZ)
[3, 2, 4]

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

>>> gf_quo_ground([3, 2, 4], 2, 5, ZZ)
[4, 1, 2]

diofant.polys.galoistools.gf_random(n, p, K)[source]

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

Examples

>>> gf_random(10, 5, ZZ) #doctest: +SKIP
[1, 2, 3, 2, 1, 1, 1, 2, 0, 4, 2]

diofant.polys.galoistools.gf_rem(f, g, p, K)[source]

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

Examples

>>> gf_rem([1, 0, 1, 1], [1, 1, 0], 2, ZZ)
[1]

diofant.polys.galoistools.gf_shoup(f, p, K)[source]

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

Examples

>>> gf_shoup([1, 4, 3], 5, ZZ)
[[1, 1], [1, 3]]

diofant.polys.galoistools.gf_sqr(f, p, K)[source]

Square polynomials in GF(p)[x].

Examples

>>> gf_sqr([3, 2, 4], 5, ZZ)
[4, 2, 3, 1, 1]

diofant.polys.galoistools.gf_sub(f, g, p, K)[source]

Subtract polynomials in GF(p)[x].

Examples

>>> gf_sub([3, 2, 4], [2, 2, 2], 5, ZZ)
[1, 0, 2]

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

>>> gf_sub_ground([3, 2, 4], 2, 5, ZZ)
[3, 2, 2]

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.

Examples

>>> gf_trace_map([1, 2], [4, 4], [1, 1], 4, [3, 2, 4], 5, ZZ)
([1, 3], [1, 3])


References

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_zassenhaus(f, p, K)[source]

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

Examples

>>> gf_zassenhaus([1, 4, 3], 5, ZZ)
[[1, 1], [1, 3]]


Manipulation of sparse, distributed polynomials¶

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

Sparse polynomials are represented as dictionaries.

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

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

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

• domain (Domain or coercible)

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

Examples

>>> R, x, y, z = ring("x y z", ZZ)
>>> R
ZZ[x,y,z]
>>> x + y + z
x + y + z

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

>>> vring("x y z", ZZ)
ZZ[x,y,z]
>>> x + y + z
x + y + z

diofant.polys.rings.sring(exprs, *symbols, **options)[source]

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

Parameters

Examples

>>> R, f = sring(x + 2*y + 3*z)
>>> R
ZZ[x,y,z]
>>> f
x + 2*y + 3*z

class diofant.polys.rings.PolyElement[source]

Element of multivariate distributed polynomial ring.

almosteq(other, tolerance=None)[source]

Approximate equality test for polynomials.

cancel(g, include=True)[source]

Cancel common factors in a rational function f/g.

Examples

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

>>> _, 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

>>> _, 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.

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

>>> 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=0)[source]

The leading degree in x or the main variable.

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

degree_list()[source]

A tuple containing leading degrees in all variables.

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

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

Computes partial derivative in x.

Examples

>>> _, x, y = ring("x y", ZZ)
>>> p = x + x**2*y**3
>>> p.diff(x)
2*x*y**3 + 1

discriminant()[source]

Computes discriminant of a polynomial.

div(fv)[source]

Division algorithm, see [CLOShea15], p. 64.

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

>>> _, 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

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

Computes indefinite integral in x.

leading_expv()[source]

Leading monomial tuple according to the monomial ordering.

Examples

>>> _, x, y, z = ring('x, y, z', ZZ)
>>> p = x**4 + x**3*y + x**2*z**2 + z**7
(4, 0, 0)

leading_monom()[source]

Leading monomial as a polynomial element.

Examples

>>> _, x, y = ring('x, y', ZZ)
x*y

leading_term()[source]

Leading term as a polynomial element.

Examples

>>> _, x, y = ring('x, y', ZZ)
3*x*y

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

>>> _, 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.

tail_degree(x=0)[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

>>> _, 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)]

total_degree()[source]

Returns the total degree.

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 Bézout’s identity in the case of integers.

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

Half extended Euclidean algorithm in $$F[x]$$.

Returns (s, h) such that h = gcd(f, g) and s*f = h (mod g).

Examples

>>> R, x = ring("x", QQ)

>>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15
>>> g = x**3 + x**2 - 4*x - 4

>>> f.half_gcdex(g)
(-1/5*x + 3/5, x + 1)

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

Extended Euclidean algorithm in $$F[x]$$.

Returns (s, t, h) such that h = gcd(f, g) and s*f + t*g = h.

Examples

>>> R, x = ring("x", QQ)

>>> f = x**4 - 2*x**3 - 6*x**2 + 12*x + 15
>>> g = x**3 + x**2 - 4*x - 4

>>> f.gcdex(g)
(-1/5*x + 3/5, 1/5*x**2 - 6/5*x + 2, x + 1)


Simplified remainder sequences¶

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

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

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

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

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

Subresultant sequence¶

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

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

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

$h = uf+vg$

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

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

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

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

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

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

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

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

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

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

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

Collins defined the subresultant remainder sequence by setting

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

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

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

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

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

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

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

Subresultant PRS algorithm in $$K[X]$$.

Examples

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

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

>>> f.subresultants(g) == [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

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

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

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

>>> R, x, y = ring("x y", ZZ)

>>> f = 3*x**2*y - y**3 - 4
>>> g = x**2 + x*y**3 - 9

>>> f.resultant(g)
-3*y**10 - 12*y**7 + y**6 - 54*y**4 + 8*y**3 + 729*y**2 - 216*y + 16

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

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

>>> 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]$$.

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

Examples

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


References

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

>>> 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 h = gcd(f, g), cff = quo(f, h), and cfg = quo(g, h).

Examples

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

>>> 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_content(f, u, K)[source]

Returns GCD of multivariate coefficients.

Examples

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

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_primitive(2*x*y + 6*x + 4*y + 12)
(2*y + 6, x + 2)


Polynomial factorization in characteristic zero:

Polynomial factorization routines in characteristic zero.

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

Factor multivariate polynomials over algebraic number fields.

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

Factor polynomials into irreducibles in $$K[X]$$.

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

Factor multivariate polynomials over finite fields.

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

Determine multiplicities of factors using trial division.

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


Examples

>>> R, x, y = ring("x y", ZZ)

>>> R.dmp_zz_factor(2*x**2 - 2*y**2)
(2, [(x - y, 1), (x + y, 1)])


References

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

Mignotte bound for multivariate polynomials in $$K[X]$$.

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

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_lead_coeffs(f, T, cs, E, H, A, u, K)[source]

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.dup_cyclotomic_p(f, K, irreducible=False)[source]

Efficiently test if f is a cyclotomic polynomial.

Examples

>>> 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_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 cyclotomic decomposition of $$f$$, which makes this method much faster that any other direct factorization approach (e.g. Zassenhaus’s).

References

diofant.polys.factortools.dup_zz_cyclotomic_poly(n, K)[source]

Efficiently generate n-th cyclotomic polynomial.

diofant.polys.factortools.dup_zz_diophantine(F, m, p, K)[source]

Wang/EEZ: Solve univariate Diophantine equations.

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


Examples

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

References

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

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

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

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

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

Test irreducibility using Eisenstein’s criterion.

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

Factor primitive square-free polynomials in $$Z[x]$$.

Gröbner basis algorithms¶

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

Gröbner bases algorithms.

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

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

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

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

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

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

References

Notes

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

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

Key for comparing critical pairs.

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

Compute the critical pair corresponding to two labeled polynomials.

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

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

F5-reduce a labeled polynomial f by B.

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

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

>>> R, x, y, z = ring("x y z", QQ, lex)

>>> f = lbp(sig(Monomial((1, 1, 1)), 4), x, 3)
>>> g = lbp(sig(Monomial((0, 0, 0)), 2), x, 2)

>>> Polyn(f).div([Polyn(g)])[1]
0
>>> f5_reduce(f, [g])
(((1, 1, 1), 4), x, 3)

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

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

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

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

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

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

References

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

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

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

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

Computes GCD of two polynomials using Gröbner bases.

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

Computes LCM of two polynomials using Gröbner bases.

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

References

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

Check if G is a Gröbner basis.

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

Checks if G is a minimal Gröbner basis.

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

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

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

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

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

Compare two labeled polynomials.

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

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

f > g otherwise

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

Key for comparing two labeled polynomials.

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

Multiply a labeled polynomial with a term.

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

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

Subtract labeled polynomial g from f.

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

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

Compute reduced Gröbner basis.

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

References

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

Compute the S-polynomial of a critical pair.

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

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

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

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

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

u > v otherwise

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

Key for comparing two signatures.

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

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

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

Multiply a signature by a monomial.

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

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

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

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

Implementation of matrix FGLM Gröbner basis conversion algorithm.

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

Algebraic number fields¶

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

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

Examples

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


References

Modular GCD¶

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

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

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

Parameters
• f (PolyElement) – multivariate integer polynomial

• g (PolyElement) – multivariate integer polynomial

Returns

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

• cff (PolyElement) – cofactor of $$f$$, i.e. $$\frac{f}{h}$$

• cfg (PolyElement) – cofactor of $$g$$, i.e. $$\frac{g}{h}$$

Examples

>>> R, x, y = ring("x, y", ZZ)

>>> modgcd((x - y)*(x + y), (x + y)**2)
(x + y, x - y, x + y)

>>> R, x, y, z = ring("x, y, z", ZZ)

>>> modgcd((x - y)*z**2, (x**2 + 1)*z)
(z, x*z - y*z, x**2 + 1)


References

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$$

Examples

>>> A = QQ.algebraic_field(sqrt(2))
>>> R, x = ring('x', A)

>>> func_field_modgcd(x**2 - 2, x + sqrt(2))
(x + sqrt(2), x - sqrt(2), 1)

>>> R, x, y = ring('x, y', A)

>>> func_field_modgcd((x + sqrt(2)*y)**2, x + sqrt(2)*y)
(x + sqrt(2)*y, x + sqrt(2)*y, 1)

>>> func_field_modgcd(x + sqrt(2)*y, x + y)
(1, x + sqrt(2)*y, x + y)


References

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

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

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

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

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

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

Returns

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

References

Heuristic GCD¶

Heuristic polynomial GCD algorithm (HEUGCD).

diofant.polys.heuristicgcd.heugcd(f, g)[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.

Examples

>>> R, x, y = ring("x y", ZZ)

>>> heugcd((x + y)**2, x*(x + y))
(x + y, x + y, x)


References

Undocumented¶

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

Options manager for Poly and public API functions.

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

Options manager for polynomial manipulation module.

Examples

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

clone(updates={})[source]

Clone self and update specified options.

class diofant.polys.polyoptions.Order[source]

order option to polynomial manipulation functions.

Configuration utilities for polynomial manipulation algorithms.

diofant.polys.polyconfig.setup(key, value=None)[source]

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

Definitions of common exceptions for polys module.

exception diofant.polys.polyerrors.BasePolynomialError[source]

Base class for polynomial related exceptions.

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

Element of multivariate distributed rational function field.

diff(x)[source]

Computes partial derivative in x.

Examples

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