多项式操作模块的内部机制

多项式模块的实现内部结构为“层级”。共有四个层级，分别称为L0、L1、L2和L3。第三和第四层包含面向用户的功能，并在上一节中进行了描述。本节重点介绍零层和一层。

第零级提供核心多项式操作功能，具有类似C的低级接口。第一级将这些低级功能封装到面向对象的结构中。这些*不是*用户看到的类，而是polys模块中内部使用的类。

在实现中存在一个额外的复杂性。这是由于所有多项式操作都是相对于一个*基础域*进行的。例如，在分解多项式 \(x^{10} - 1\) 时，必须决定系数应属于哪个环，或者更不明显的是，分解中允许出现哪些系数。这种系数的选择称为基础域。典型的选择包括整数 \(\mathbb{Z}\)、有理数 \(\mathbb{Q}\) 或各种相关的环和域。但在多项式环（如 \(k[Y]\)，其中 \(k\) 是某个固定域）上进行分解也是完全合法的（尽管在这种情况下并不有趣）。

因此，多项式操作算法（无论是像因式分解这样的复杂算法，还是像加法或乘法这样的简单算法）都必须依赖其他代码来操作系数。在多项式操作模块中，这种代码被封装在所谓的“域”中。域基本上是一个工厂对象：它接受各种数据表示，并将它们转换为具有统一接口的对象。域创建的每个对象都必须实现算术运算 \(+\)、\(-\) 和 \(\times\)。其他操作通过域访问，例如在 ZZ.quo(ZZ(4), ZZ(2)) 中。

需要注意的是，存在一定程度的*循环性*：多项式环域使用一级类，一级类使用零级函数，而零级函数使用域。原则上这是可能的，但在当前的实现中是不可能的，例如在像 \(k[X][Y]\) 这样的环中工作。这将创建更多的层次。因此，在同构环 \(k[X, Y]\) 中工作是首选。

零级

零级包含多项式操作模块的主要代码。

密集多元多项式的操作

这些函数可用于操作 \(K[X_0, \ldots, X_u]\) 中的多项式。用于操作密集表示的多变量多项式的函数前缀为 dmp_。仅适用于单变量多项式（即 \(u = 0\)）的函数前缀为 dup__。基本域 \(K\) 必须显式传递。对于许多多变量多项式操作函数，还必须传递层级 \(u\)，即生成元数量减一。（注意，在许多情况下，提供了 dup_ 版本的函数，这些函数可能略微更高效。）

基本操作：

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

返回 f 的首项系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import poly_LC

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

sympy.polys.densebasic.dmp_TC(f, K)

返回 f 的尾系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import poly_TC

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

sympy.polys.densebasic.dmp_ground_LC(f, u, K)

返回地导系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_ground_LC

>>> f = ZZ.map([[[1], [2, 3]]])

>>> dmp_ground_LC(f, 2, ZZ)
1

sympy.polys.densebasic.dmp_ground_TC(f, u, K)

返回尾随系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_ground_TC

>>> f = ZZ.map([[[1], [2, 3]]])

>>> dmp_ground_TC(f, 2, ZZ)
3

sympy.polys.densebasic.dmp_true_LT(f, u, K)

返回首项 c * x_1**n_1 ... x_k**n_k。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_true_LT

>>> f = ZZ.map([[4], [2, 0], [3, 0, 0]])

>>> dmp_true_LT(f, 1, ZZ)
((2, 0), 4)

sympy.polys.densebasic.dmp_degree(f, u)

返回 f 在 x_0 在 K[X] 中的前导次数。

注意，0 度是负无穷大（float('-inf')）。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree

>>> dmp_degree([[[]]], 2)
-inf

>>> f = ZZ.map([[2], [1, 2, 3]])

>>> dmp_degree(f, 1)
1

sympy.polys.densebasic.dmp_degree_in(f, j, u)

返回 f 在 K[X] 中关于 x_j 的首项次数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree_in

>>> f = ZZ.map([[2], [1, 2, 3]])

>>> dmp_degree_in(f, 0, 1)
1
>>> dmp_degree_in(f, 1, 1)
2

sympy.polys.densebasic.dmp_degree_list(f, u)

返回 K[X] 中 f 的度数列表。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_degree_list

>>> f = ZZ.map([[1], [1, 2, 3]])

>>> dmp_degree_list(f, 1)
(1, 2)

sympy.polys.densebasic.dmp_strip(f, u)

从 K[X] 中的 f 移除前导零。

示例

>>> from sympy.polys.densebasic import dmp_strip

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

sympy.polys.densebasic.dmp_validate(f, K=None)

返回 f 中的层级数并递归地剥离它。

示例

>>> from sympy.polys.densebasic import dmp_validate

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

sympy.polys.densebasic.dup_reverse(f)

计算 x**n * f(1/x)，即：在 K[x] 中反转 f。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dup_reverse

>>> f = ZZ.map([1, 2, 3, 0])

>>> dup_reverse(f)
[3, 2, 1]

sympy.polys.densebasic.dmp_copy(f, u)

在 K[X] 中创建多项式 f 的新副本。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_copy

>>> f = ZZ.map([[1], [1, 2]])

>>> dmp_copy(f, 1)
[[1], [1, 2]]

sympy.polys.densebasic.dmp_to_tuple(f, u)

将 \(f\) 转换为嵌套的元组。

这是用于哈希的。这与 dmp_copy() 类似。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_to_tuple

>>> f = ZZ.map([[1], [1, 2]])

>>> dmp_to_tuple(f, 1)
((1,), (1, 2))

sympy.polys.densebasic.dmp_normal(f, u, K)

在给定域中标准化多元多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_normal

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

sympy.polys.densebasic.dmp_convert(f, u, K0, K1)

将 f 的地面域从 K0 转换为 K1。

示例

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_convert

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

sympy.polys.densebasic.dmp_from_sympy(f, u, K)

将 f 的地面域从 SymPy 转换为 K。

示例

>>> from sympy import S
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_from_sympy

>>> dmp_from_sympy([[S(1)], [S(2)]], 1, ZZ) == [[ZZ(1)], [ZZ(2)]]
True

sympy.polys.densebasic.dmp_nth(f, n, u, K)

返回 f 在 K[x] 中的第 n 个系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_nth

>>> f = ZZ.map([[1], [2], [3]])

>>> dmp_nth(f, 0, 1, ZZ)
[3]
>>> dmp_nth(f, 4, 1, ZZ)
[]

sympy.polys.densebasic.dmp_ground_nth(f, N, u, K)

返回 f 在 K[x] 中的第 n 个常数项。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_ground_nth

>>> f = ZZ.map([[1], [2, 3]])

>>> dmp_ground_nth(f, (0, 1), 1, ZZ)
2

sympy.polys.densebasic.dmp_zero_p(f, u)

如果 f 在 K[X] 中为零，则返回 True。

示例

>>> from sympy.polys.densebasic import dmp_zero_p

>>> dmp_zero_p([[[[[]]]]], 4)
True
>>> dmp_zero_p([[[[[1]]]]], 4)
False

sympy.polys.densebasic.dmp_zero(u)

返回一个多元零值。

示例

>>> from sympy.polys.densebasic import dmp_zero

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

sympy.polys.densebasic.dmp_one_p(f, u, K)

如果 f 是 K[X] 中的一个，则返回 True。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_one_p

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

sympy.polys.densebasic.dmp_one(u, K)

返回一个在 K 上的多元数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_one

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

sympy.polys.densebasic.dmp_ground_p(f, c, u)

如果 f 在 K[X] 中是常数，则返回 True。

示例

>>> from sympy.polys.densebasic import dmp_ground_p

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

sympy.polys.densebasic.dmp_ground(c, u)

返回一个多元常数。

示例

>>> from sympy.polys.densebasic import dmp_ground

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

sympy.polys.densebasic.dmp_zeros(n, u, K)

返回一个多元零的列表。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_zeros

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

sympy.polys.densebasic.dmp_grounds(c, n, u)

返回一个多元常数列表。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_grounds

>>> dmp_grounds(ZZ(4), 3, 2)
[[[[4]]], [[[4]]], [[[4]]]]
>>> dmp_grounds(ZZ(4), 3, -1)
[4, 4, 4]

sympy.polys.densebasic.dmp_negative_p(f, u, K)

如果 LC(f) 为负，则返回 True。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_negative_p

>>> dmp_negative_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
False
>>> dmp_negative_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
True

sympy.polys.densebasic.dmp_positive_p(f, u, K)

如果 LC(f) 为正，则返回 True。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_positive_p

>>> dmp_positive_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
True
>>> dmp_positive_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
False

sympy.polys.densebasic.dmp_from_dict(f, u, K)

从 dict 创建一个 K[X] 多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_from_dict

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

sympy.polys.densebasic.dmp_to_dict(f, u, K=None, zero=False)

将 K[X] 多项式转换为 dict。

示例

>>> from sympy.polys.densebasic import dmp_to_dict

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

sympy.polys.densebasic.dmp_swap(f, i, j, u, K)

将 K[..x_i..x_j..] 转换为 K[..x_j..x_i..]。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_swap

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

sympy.polys.densebasic.dmp_permute(f, P, u, K)

返回一个多项式在 K[x_{P(1)},..,x_{P(n)}] 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_permute

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

sympy.polys.densebasic.dmp_nest(f, l, K)

返回一个嵌套 l 层的多变量值。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_nest

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

sympy.polys.densebasic.dmp_raise(f, l, u, K)

返回一个提升 l 级的多元多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_raise

>>> f = ZZ.map([[], [1, 2]])

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

sympy.polys.densebasic.dmp_deflate(f, u, K)

在 K[X] 的多项式中将 x_i**m_i 映射到 y_i。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_deflate

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

>>> dmp_deflate(f, 1, ZZ)
((2, 3), [[1, 2], [3, 4]])

sympy.polys.densebasic.dmp_multi_deflate(polys, u, K)

在 K[X] 中的一组多项式中，将 x_i**m_i 映射到 y_i。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_multi_deflate

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

sympy.polys.densebasic.dmp_inflate(f, M, u, K)

在多项式 K[X] 中将 y_i 映射到 x_i**k_i。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_inflate

>>> f = ZZ.map([[1, 2], [3, 4]])

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

sympy.polys.densebasic.dmp_exclude(f, u, K)

从 f 中排除无用的层级。

返回排除的级别，新的排除 f，以及新的 u。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_exclude

>>> f = ZZ.map([[[1]], [[1], [2]]])

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

sympy.polys.densebasic.dmp_include(f, J, u, K)

在 f 中包含无用的级别。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_include

>>> f = ZZ.map([[1], [1, 2]])

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

sympy.polys.densebasic.dmp_inject(f, u, K, front=False)

将 f 从 K[X][Y] 转换为 K[X,Y]。

示例

>>> from sympy.polys.rings import ring
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_inject

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

sympy.polys.densebasic.dmp_eject(f, u, K, front=False)

将 f 从 K[X,Y] 转换为 K[X][Y]。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_eject

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

sympy.polys.densebasic.dmp_terms_gcd(f, u, K)

从 K[X] 中的 f 中去除项的最大公约数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_terms_gcd

>>> f = ZZ.map([[1, 0], [1, 0, 0], [], []])

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

sympy.polys.densebasic.dmp_list_terms(f, u, K, order=None)

按给定的顺序 order 列出 f 中的所有非零项。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_list_terms

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

sympy.polys.densebasic.dmp_apply_pairs(f, g, h, args, u, K)

对 f 和 g 的系数对应用 h。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dmp_apply_pairs

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

sympy.polys.densebasic.dmp_slice(f, m, n, u, K)

在 K[X] 中取 f 的连续子序列项。

sympy.polys.densebasic.dup_random(n, a, b, K)

返回一个次数为 n 且系数在 [a, b] 范围内的多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densebasic import dup_random

>>> dup_random(3, -10, 10, ZZ) 
[-2, -8, 9, -4]

算术运算：

sympy.polys.densearith.dmp_add_term(f, c, i, u, K)

在 K[X] 中，将 c(x_2..x_u)*x_0**i 添加到 f 中。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_sub_term(f, c, i, u, K)

在 K[X] 中从 f 中减去 c(x_2..x_u)*x_0**i。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_mul_term(f, c, i, u, K)

在 K[X] 中将 f 乘以 c(x_2..x_u)*x_0**i。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_add_ground(f, c, u, K)

将一个地面域的元素添加到 f 中。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_sub_ground(f, c, u, K)

从 f 中减去地面域的一个元素。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_mul_ground(f, c, u, K)

在 K[X] 中将 f 乘以一个常数值。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_mul_ground(2*x + 2*y, ZZ(3))
6*x + 6*y

sympy.polys.densearith.dmp_quo_ground(f, c, u, K)

在 K[X] 中通过常数进行商运算。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densearith.dmp_exquo_ground(f, c, u, K)

在 K[X] 中通过常数进行精确除法。

示例

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> R.dmp_exquo_ground(x**2*y + 2*x, QQ(2))
1/2*x**2*y + x

sympy.polys.densearith.dup_lshift(f, n, K)

在 K[x] 中高效地将 f 乘以 x**n。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

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

sympy.polys.densearith.dup_rshift(f, n, K)

在 K[x] 中高效地将 f 除以 x**n。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_abs(f, u, K)

在 K[X] 中使所有系数为正。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_neg(f, u, K)

在 K[X] 中否定一个多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_add(f, g, u, K)

在 K[X] 中添加稠密多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_add(x**2 + y, x**2*y + x)
x**2*y + x**2 + x + y

sympy.polys.densearith.dmp_sub(f, g, u, K)

在 K[X] 中减去稠密多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_add_mul(f, g, h, u, K)

返回 f + g*h 其中 f, g, h 在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_add_mul(x**2 + y, x, x + 2)
2*x**2 + 2*x + y

sympy.polys.densearith.dmp_sub_mul(f, g, h, u, K)

返回 f - g*h ，其中 f, g, h 在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_mul(f, g, u, K)

在 K[X] 中乘以稠密多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_sqr(f, u, K)

K[X] 中的平方稠密多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_pow(f, n, u, K)

在 K[X] 中将 f 提升到 n 次方。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_pdiv(f, g, u, K)

多项式伪除法在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

sympy.polys.densearith.dmp_prem(f, g, u, K)

多项式伪余数在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_pquo(f, g, u, K)

多项式在 K[X] 中的精确伪商。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densearith.dmp_pexquo(f, g, u, K)

多项式伪商在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> 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], []]

sympy.polys.densearith.dmp_rr_div(f, g, u, K)

环上的多元带余除法。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_rr_div(x**2 + x*y, 2*x + 2)
(0, x**2 + x*y)

sympy.polys.densearith.dmp_ff_div(f, g, u, K)

域上的多项式带余除法。

示例

>>> from sympy.polys import ring, QQ
>>> 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)

sympy.polys.densearith.dmp_div(f, g, u, K)

在 K[X] 中的多项式带余除法。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densearith.dmp_rem(f, g, u, K)

返回 K[X] 中的多项式余数。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densearith.dmp_quo(f, g, u, K)

返回 K[X] 中的精确多项式商。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densearith.dmp_exquo(f, g, u, K)

返回多项式商在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> 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], []]

sympy.polys.densearith.dmp_max_norm(f, u, K)

返回 K[X] 中多项式的最大范数。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_l1_norm(f, u, K)

返回 K[X] 中多项式的 l1 范数。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densearith.dmp_expand(polys, u, K)

在 K[X] 中将几个多项式相乘。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

其他工具：

sympy.polys.densetools.dmp_integrate(f, m, u, K)

计算 f 在 x_0 在 K[X] 中的不定积分。

示例

>>> from sympy.polys import ring, QQ
>>> 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

sympy.polys.densetools.dmp_integrate_in(f, m, j, u, K)

计算 f 在 K[X] 中 x_j 的不定积分。

示例

>>> from sympy.polys import ring, QQ
>>> 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

sympy.polys.densetools.dmp_diff(f, m, u, K)

m 阶导数在 x_0 处的一个多项式在 K[X] 中。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_diff_in(f, m, j, u, K)

m 阶导数在 x_j 中对 K[X] 中的多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_eval(f, a, u, K)

使用 Horner 方案在 K[X] 中对 x_0 = a 处的多项式进行求值。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> R.dmp_eval(2*x*y + 3*x + y + 2, 2)
5*y + 8

sympy.polys.densetools.dmp_eval_in(f, a, j, u, K)

使用Horner方案在 K[X] 中对 x_j = a 处的多项式进行求值。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_eval_tail(f, A, u, K)

在 K[X] 中，计算多项式在 x_j = a_j, ... 处的值。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_diff_eval_in(f, m, a, j, u, K)

在 K[X] 中对 x_j 进行多项式的微分和在 a 处的求值。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_trunc(f, p, u, K)

将 K[X] 多项式对 K[Y] 中的多项式 p 取模。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_ground_trunc(f, p, u, K)

将 K[X] 多项式对 K 中的常数 p 取模。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dup_monic(f, K)

在 K[x] 中将所有系数除以 LC(f)。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densetools.dmp_ground_monic(f, u, K)

在 K[X] 中将所有系数除以 LC(f)。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densetools.dup_content(f, K)

计算 f 在 K[x] 中的系数的最大公约数。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densetools.dmp_ground_content(f, u, K)

计算 K[X] 中 f 的系数的最大公约数。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densetools.dup_primitive(f, K)

计算内容和 f 在 K[x] 中的原始形式。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densetools.dmp_ground_primitive(f, u, K)

计算内容和 f 在 K[X] 中的原始形式。

示例

>>> from sympy.polys import ring, ZZ, QQ

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

sympy.polys.densetools.dup_extract(f, g, K)

从 K[x] 中的一对多项式中提取公共内容。

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

sympy.polys.densetools.dmp_ground_extract(f, g, u, K)

从 K[X] 中的一对多项式中提取公共内容。

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

sympy.polys.densetools.dup_real_imag(f, K)

找到 f1 和 f2，使得 f(x+I*y) = f1(x,y) + f2(x,y)*I。

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

>>> from sympy.abc import x, y, z
>>> from sympy import I
>>> (z**3 + z**2 + z + 1).subs(z, x+I*y).expand().collect(I)
x**3 + x**2 - 3*x*y**2 + x - y**2 + I*(3*x**2*y + 2*x*y - y**3 + y) + 1

sympy.polys.densetools.dup_mirror(f, K)

在 K[x] 中高效地计算组合 f(-x)。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_mirror(x**3 + 2*x**2 - 4*x + 2)
-x**3 + 2*x**2 + 4*x + 2

sympy.polys.densetools.dup_scale(f, a, K)

在 K[x] 中高效地计算组合 f(a*x)。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

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

sympy.polys.densetools.dup_shift(f, a, K)

高效评估 K[x] 中的泰勒平移 f(x + a)。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

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

sympy.polys.densetools.dup_transform(f, p, q, K)

在 K[x] 中评估函数变换 q**n * f(p/q)。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.densetools.dmp_compose(f, g, u, K)

在 K[X] 中评估函数组合 f(g)。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.densetools.dup_decompose(f, K)

在 K[x] 中计算 f 的功能分解。

给定一个系数在特征为零的域中的单变量多项式 f，返回列表 [f_1, f_2, ..., f_n]，其中:

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

而 f_2, ..., f_n 是至少为二次的单项式和齐次多项式。

与因式分解不同，多项式的完全函数分解不是唯一的，考虑以下例子：

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

其中 T_n 和 T_m 是切比雪夫多项式。

参考文献

[1]

[Kozen89]

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

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

sympy.polys.densetools.dmp_lift(f, u, K)

在 K[X] 中将代数系数转换为整数。

示例

>>> from sympy.polys import ring, QQ
>>> from sympy 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**4 + x**2 + 4*x + 4

sympy.polys.densetools.dup_sign_variations(f, K)

计算 f 在 K[x] 中的符号变化次数。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

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

sympy.polys.densetools.dmp_clear_denoms(f, u, K0, K1=None, convert=False)

清除分母，即转换 K_0 为 K_1。

示例

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> f = QQ(1,2)*x + QQ(1,3)*y + 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)

sympy.polys.densetools.dmp_revert(f, g, u, K)

使用牛顿迭代法计算 f**(-1) 模 x**n。

示例

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

有限域系数的多项式操作

此模块中的函数带有前缀 gf_，这是指有限域的经典名称“Galois Fields”。请注意，许多多项式因式分解算法通过归约到有限域的情况来工作，因此为这种情况提供特殊的实现既合理又必要，这不仅出于性能考虑，还因为某些方法在一般域上甚至没有意义。

sympy.polys.galoistools.gf_crt(U, M, K=None)

中国剩余定理。

给定一组整数余数 u_0,...,u_n 和一组互质整数模数 m_0,...,m_n，返回一个整数 u，使得 u = u_i mod m_i 对于 i = ``0,...,n。

参见

sympy.ntheory.modular.crt

更高级别的crt例程

sympy.ntheory.modular.solve_congruence

示例

考虑一组余数 U = [49, 76, 65] 和一组模数 M = [99, 97, 95]。那么我们有:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_crt

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

这是正确结果，因为:

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

注意：这是一个没有错误检查的底层例程。

sympy.polys.galoistools.gf_crt1(M, K)

中国剩余定理的第一部分。

参见

sympy.ntheory.modular.crt1

更高级别的crt例程

sympy.polys.galoistools.gf_crt

sympy.polys.galoistools.gf_crt2

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_crt, gf_crt1, gf_crt2
>>> U = [49, 76, 65]
>>> M = [99, 97, 95]

以下两个代码具有相同的结果。

>>> gf_crt(U, M, ZZ)
639985

>>> p, E, S = gf_crt1(M, ZZ)
>>> gf_crt2(U, M, p, E, S, ZZ)
639985

然而，当我们想要固定 M 并计算多个 U 时，速度会更快，即以下情况：

>>> p, E, S = gf_crt1(M, ZZ)
>>> Us = [[49, 76, 65], [23, 42, 67]]
>>> for U in Us:
...     print(gf_crt2(U, M, p, E, S, ZZ))
639985
236237

sympy.polys.galoistools.gf_crt2(U, M, p, E, S, K)

中国剩余定理的第二部分。

参见 gf_crt1 以了解用法。

参见

sympy.ntheory.modular.crt2

更高级别的crt例程

sympy.polys.galoistools.gf_crt

sympy.polys.galoistools.gf_crt1

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_crt2

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

sympy.polys.galoistools.gf_int(a, p)

将 a mod p 强制转换为范围在 [-p/2, p/2] 内的整数。

示例

>>> from sympy.polys.galoistools import gf_int

>>> gf_int(2, 7)
2
>>> gf_int(5, 7)
-2

sympy.polys.galoistools.gf_degree(f)

返回 f 的领先次数。

示例

>>> from sympy.polys.galoistools import gf_degree

>>> gf_degree([1, 1, 2, 0])
3
>>> gf_degree([])
-1

sympy.polys.galoistools.gf_LC(f, K)

返回 f 的首项系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_LC

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

sympy.polys.galoistools.gf_TC(f, K)

返回 f 的尾系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_TC

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

sympy.polys.galoistools.gf_strip(f)

从 f 中移除前导零。

示例

>>> from sympy.polys.galoistools import gf_strip

>>> gf_strip([0, 0, 0, 3, 0, 1])
[3, 0, 1]

sympy.polys.galoistools.gf_trunc(f, p)

将所有系数对 p 取模。

示例

>>> from sympy.polys.galoistools import gf_trunc

>>> gf_trunc([7, -2, 3], 5)
[2, 3, 3]

sympy.polys.galoistools.gf_normal(f, p, K)

在 K 中标准化所有系数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_normal

>>> gf_normal([5, 10, 21, -3], 5, ZZ)
[1, 2]

sympy.polys.galoistools.gf_from_dict(f, p, K)

从字典创建一个 GF(p)[x] 多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_from_dict

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

sympy.polys.galoistools.gf_to_dict(f, p, symmetric=True)

将 GF(p)[x] 多项式转换为字典。

示例

>>> from sympy.polys.galoistools import gf_to_dict

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

sympy.polys.galoistools.gf_from_int_poly(f, p)

从 Z[x] 创建一个 GF(p)[x] 多项式。

示例

>>> from sympy.polys.galoistools import gf_from_int_poly

>>> gf_from_int_poly([7, -2, 3], 5)
[2, 3, 3]

sympy.polys.galoistools.gf_to_int_poly(f, p, symmetric=True)

将 GF(p)[x] 多项式转换为 Z[x]。

示例

>>> from sympy.polys.galoistools import gf_to_int_poly

>>> gf_to_int_poly([2, 3, 3], 5)
[2, -2, -2]
>>> gf_to_int_poly([2, 3, 3], 5, symmetric=False)
[2, 3, 3]

sympy.polys.galoistools.gf_neg(f, p, K)

在 GF(p)[x] 中否定一个多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_neg

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

sympy.polys.galoistools.gf_add_ground(f, a, p, K)

计算 f + a 其中 f 在 GF(p)[x] 中，a 在 GF(p) 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_add_ground

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

sympy.polys.galoistools.gf_sub_ground(f, a, p, K)

计算 f - a 其中 f 在 GF(p)[x] 中，a 在 GF(p) 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sub_ground

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

sympy.polys.galoistools.gf_mul_ground(f, a, p, K)

计算 f * a 其中 f 在 GF(p)[x] 中，a 在 GF(p) 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_mul_ground

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

sympy.polys.galoistools.gf_quo_ground(f, a, p, K)

计算 f/a 其中 f 在 GF(p)[x] 中，a 在 GF(p) 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_quo_ground

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

sympy.polys.galoistools.gf_add(f, g, p, K)

在 GF(p)[x] 中添加多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_add

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

sympy.polys.galoistools.gf_sub(f, g, p, K)

在 GF(p)[x] 中减去多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sub

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

sympy.polys.galoistools.gf_mul(f, g, p, K)

在 GF(p)[x] 中乘多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_mul

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

sympy.polys.galoistools.gf_sqr(f, p, K)

GF(p)[x] 中的多项式平方。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sqr

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

sympy.polys.galoistools.gf_add_mul(f, g, h, p, K)

返回 f + g*h 其中 f, g, h 在 GF(p)[x] 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_add_mul
>>> gf_add_mul([3, 2, 4], [2, 2, 2], [1, 4], 5, ZZ)
[2, 3, 2, 2]

sympy.polys.galoistools.gf_sub_mul(f, g, h, p, K)

计算 f - g*h 其中 f, g, h 在 GF(p)[x] 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sub_mul

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

sympy.polys.galoistools.gf_expand(F, p, K)

在 GF(p)[x] 中展开 factor() 的结果。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_expand

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

sympy.polys.galoistools.gf_div(f, g, p, K)

在 GF(p)[x] 中的带余除法。

给定系数在具有 p 个元素的有限域中的单变量多项式 f 和 g ，返回多项式 q 和 r （商和余数），使得 f = q*g + r。

考虑在 GF(2) 中的多项式 x**3 + x + 1 和 x**2 + x:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_div, gf_add_mul

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

结果我们得到了商 x + 1 和余数 1，因此:

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

参考文献

[1]

[Monagan93]

[2]

[Gathen99]

sympy.polys.galoistools.gf_rem(f, g, p, K)

在 GF(p)[x] 中计算多项式余数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_rem

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

sympy.polys.galoistools.gf_quo(f, g, p, K)

在 GF(p)[x] 中计算精确商。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_quo

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

sympy.polys.galoistools.gf_exquo(f, g, p, K)

在 GF(p)[x] 中计算多项式商。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_exquo

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

sympy.polys.galoistools.gf_lshift(f, n, K)

高效地将 f 乘以 x**n。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_lshift

>>> gf_lshift([3, 2, 4], 4, ZZ)
[3, 2, 4, 0, 0, 0, 0]

sympy.polys.galoistools.gf_rshift(f, n, K)

高效地将 f 除以 x**n。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_rshift

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

sympy.polys.galoistools.gf_pow(f, n, p, K)

使用重复平方计算 GF(p)[x] 中的 f**n。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_pow

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

sympy.polys.galoistools.gf_pow_mod(f, n, g, p, K)

在 GF(p)[x]/(g) 中使用重复平方计算 f**n。

给定多项式 f 和 g 在 GF(p)[x] 中，以及一个非负整数 n，使用重复平方算法高效计算 f**n (mod g)，即 f**n 除以 g 的余数。

参考文献

[1]

[Gathen99]

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_pow_mod

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

sympy.polys.galoistools.gf_gcd(f, g, p, K)

欧几里得算法在 GF(p)[x] 中。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_gcd

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

sympy.polys.galoistools.gf_lcm(f, g, p, K)

在 GF(p)[x] 中计算多项式的最小公倍数。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_lcm

>>> gf_lcm(ZZ.map([3, 2, 4]), ZZ.map([2, 2, 3]), 5, ZZ)
[1, 2, 0, 4]

sympy.polys.galoistools.gf_cofactors(f, g, p, K)

在 GF(p)[x] 中计算多项式的最大公约数和余因子。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_cofactors

>>> gf_cofactors(ZZ.map([3, 2, 4]), ZZ.map([2, 2, 3]), 5, ZZ)
([1, 3], [3, 3], [2, 1])

sympy.polys.galoistools.gf_gcdex(f, g, p, K)

扩展欧几里得算法在 GF(p)[x] 中。

给定多项式 f 和 g 在 GF(p)[x] 中，计算多项式 s、t 和 h，使得 h = gcd(f, g) 且 s*f + t*g = h。EEA 的典型应用是求解多项式丢番图方程。

考虑多项式 f = (x + 7) (x + 1), g = (x + 7) (x**2 + 1) 在 GF(11)[x] 中。应用扩展欧几里得算法得到:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_gcdex, gf_mul, gf_add

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

结果我们得到了多项式 s = 5*x + 6 和 t = 6，并且额外得到了 gcd(f, g) = x + 7。这是正确的，因为:

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

参考文献

[1]

[Gathen99]

sympy.polys.galoistools.gf_monic(f, p, K)

计算 GF(p)[x] 中的 LC 和一个首一多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_monic

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

sympy.polys.galoistools.gf_diff(f, p, K)

在 GF(p)[x] 中对多项式求导。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_diff

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

sympy.polys.galoistools.gf_eval(f, a, p, K)

使用Horner方案在 GF(p) 中计算 f(a)。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_eval

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

sympy.polys.galoistools.gf_multi_eval(f, A, p, K)

计算 f(a) 对于 a 在 [a_1, ..., a_n] 中的值。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_multi_eval

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

sympy.polys.galoistools.gf_compose(f, g, p, K)

在 GF(p)[x] 中计算多项式复合 f(g)。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_compose

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

sympy.polys.galoistools.gf_compose_mod(g, h, f, p, K)

在 GF(p)[x]/(f) 中计算多项式组合 g(h)。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_compose_mod

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

sympy.polys.galoistools.gf_trace_map(a, b, c, n, f, p, K)

在 GF(p)[x]/(f) 中计算多项式迹映射。

给定多项式 f 在 GF(p)[x] 中，多项式 a, b, c 在商环 GF(p)[x]/(f) 中，使得对于某个 p 的正整数幂 t，有 b = c**t (mod f)，以及一个正整数 n，返回一个映射:

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

在因式分解的上下文中，b = x**p mod f 和 c = x mod f。这样我们可以在等度因式分解例程中高效地计算迹多项式，比其他方法（如迭代 Frobenius 算法）快得多，特别是对于高次多项式。

参考文献

[1]

[Gathen92]

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_trace_map

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

sympy.polys.galoistools.gf_random(n, p, K)

在 GF(p)[x] 中生成一个度为 n 的随机多项式。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_random
>>> gf_random(10, 5, ZZ) 
[1, 2, 3, 2, 1, 1, 1, 2, 0, 4, 2]

sympy.polys.galoistools.gf_irreducible(n, p, K)

在 GF(p)[x] 中生成随机不可约多项式，次数为 n。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_irreducible
>>> gf_irreducible(10, 5, ZZ) 
[1, 4, 2, 2, 3, 2, 4, 1, 4, 0, 4]

sympy.polys.galoistools.gf_irreducible_p(f, p, K)

测试多项式 f 在 GF(p)[x] 中的不可约性。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_irreducible_p

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

sympy.polys.galoistools.gf_sqf_p(f, p, K)

如果 f 在 GF(p)[x] 中是无平方的，则返回 True。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sqf_p

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

sympy.polys.galoistools.gf_sqf_part(f, p, K)

返回 GF(p)[x] 多项式的无平方部分。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_sqf_part

>>> gf_sqf_part(ZZ.map([1, 1, 3, 0, 1, 0, 2, 2, 1]), 5, ZZ)
[1, 4, 3]

sympy.polys.galoistools.gf_sqf_list(f, p, K, all=False)

返回 GF(p)[x] 多项式的无平方分解。

给定一个多项式 f 在 GF(p)[x] 中，返回 f 的首项系数和一个无平方分解 f_1**e_1 f_2**e_2 ... f_k**e_k ，使得所有 f_i 都是首一多项式，并且对于 i != j ， (f_i, f_j) 是互质的， e_1 ... e_k 按递增顺序给出。所有平凡项（即 f_i = 1 ）都不包含在输出中。

考虑多项式 f = x**11 + 1 在 GF(11)[x] 上:

>>> from sympy.polys.domains import ZZ

>>> from sympy.polys.galoistools import (
...     gf_from_dict, gf_diff, gf_sqf_list, gf_pow,
... )
... 

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

注意 f'(x) = 0:

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

这种现象在特征值为零的情况下不会发生。然而，我们仍然可以使用 gf_sqf() 计算 f 的无平方分解:

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

我们得到了因式分解 f = (x + 1)**11。这是正确的，因为:

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

参考文献

[1]

[Geddes92]

sympy.polys.galoistools.gf_Qmatrix(f, p, K)

计算 Berlekamp 的 Q 矩阵。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_Qmatrix

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

sympy.polys.galoistools.gf_Qbasis(Q, p, K)

计算 Q 的核的基。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_Qmatrix, gf_Qbasis

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

sympy.polys.galoistools.gf_berlekamp(f, p, K)

在 GF(p)[x] 中对无平方 f 进行因式分解，其中 p 较小。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_berlekamp

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

sympy.polys.galoistools.gf_zassenhaus(f, p, K)

在中等大小的 p 下，在 GF(p)[x] 中对无平方因子多项式 f 进行因式分解。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_zassenhaus

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

sympy.polys.galoistools.gf_shoup(f, p, K)

在 GF(p)[x] 中对大 p 进行无平方因子的 f 分解。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_shoup

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

sympy.polys.galoistools.gf_factor_sqf(f, p, K, method=None)

在 GF(p)[x] 中对无平方多项式 f 进行因式分解。

示例

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_factor_sqf

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

sympy.polys.galoistools.gf_factor(f, p, K)

在 GF(p)[x] 中分解（非无平方因子）多项式。

给定一个可能在 GF(p)[x] 中的非平方自由多项式 f，返回其完全不可约分解:

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

其中每个 f_i 都是一个首一多项式，并且对于 i != j，有 gcd(f_i, f_j) == 1。结果以一个元组的形式给出，该元组包含 f 的首项系数和 f 的因子的列表及其重数。

该算法首先计算 f 的无平方分解，然后迭代地分解每个无平方因子。

考虑一个非平方自由多项式 f = (7*x + 1) (x + 2)**2 在 GF(11)[x] 中。我们如下获得其不可约因式分解:

>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.galoistools import gf_factor

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

我们得到了因式分解 f = 5 (x + 2) (x + 8)**2。我们没有恢复输入多项式的确切形式，因为我们要求分别得到 f 的单位因子及其首项系数。

f 的无平方因子可以通过三种非常不同的方法分解为 GF(p) 上的不可约因子：

伯利坎普

对于非常小的 p 值（通常 p < 25），它是高效的。

康托尔-扎森豪斯

在平均输入效率高，并且对于“典型”的 p

Shoup-Kaltofen-Gathen

高效处理非常大的输入和模数

如果你想使用特定的因式分解方法，而不是默认的方法，请将 GF_FACTOR_METHOD 设置为 berlekamp、zassenhaus 或 shoup 中的一个值。

参考文献

[1]

[Gathen99]

sympy.polys.galoistools.gf_value(f, a)

多项式 ‘f’ 在域 R 中 ‘a’ 处的值。

示例

>>> from sympy.polys.galoistools import gf_value

>>> gf_value([1, 7, 2, 4], 11)
2204

sympy.polys.galoistools.gf_csolve(f, n)

求解 f(x) 同余 0 mod(n)。

n 被分解为规范因子，并且对于每个因子，将求解 f(x) ≡ 0 mod(p**e)。将中国剩余定理应用于结果，返回最终答案。

参见

sympy.ntheory.residue_ntheory.polynomial_congruence

更高层次的求解例程

参考文献

[1]

‘数论导论’ 第五版，作者：Ivan Niven, Zuckerman 和 Montgomery。

示例

求解 [1, 1, 7] 同余 0 mod(189)：

>>> from sympy.polys.galoistools import gf_csolve
>>> gf_csolve([1, 1, 7], 189)
[13, 49, 76, 112, 139, 175]

稀疏、分布式多项式和向量的操作

密集表示形式如果变量数量增加，会迅速需要不可行的存储量和计算时间。因此，有代码用于以 稀疏 表示形式操作多项式。Ring对象和元素由类 PolyRing 和 PolyElement 实现。

在交换代数中，人们不仅研究多项式，还研究多项式环上的*模*。多项式操作模块为有限生成的自由模提供了基本的低级支持。这主要用于Groebner基计算（参见相关内容），因此仅提供了所需程度上的操作函数。它们带有前缀``sdm_``。请注意，在示例中，自由模的生成元被称为`f_1, f_2, ldots`。

sympy.polys.distributedmodules.sdm_monomial_mul(M, X)

将表示 \(K[X]\) 中单项式的元组 X 乘以表示 \(F\) 中单项式的元组 M。

示例

将 \(xy^3\) 乘以 \(x f_1\) 得到 \(x^2 y^3 f_1\)：

>>> from sympy.polys.distributedmodules import sdm_monomial_mul
>>> sdm_monomial_mul((1, 1, 0), (1, 3))
(1, 2, 3)

sympy.polys.distributedmodules.sdm_monomial_deg(M)

返回 M 的总度数。

示例

例如，\(x^2 y f_5\) 的总次数是 3：

>>> from sympy.polys.distributedmodules import sdm_monomial_deg
>>> sdm_monomial_deg((5, 2, 1))
3

sympy.polys.distributedmodules.sdm_monomial_divides(A, B)

是否存在一个（多项式）单项式 X，使得 XA = B？

示例

正面例子：

在以下示例中，单项式以 x、y 和生成器 f_1、f_2 等表示。该单项式的元组形式用于调用 sdm_monomial_divides。注意：生成器在表达式中最后出现，但在元组中首先出现，其他因子按其在单项式表达式中出现的顺序出现。

\(A = f_1\) 除以 \(B = f_1\)

>>> from sympy.polys.distributedmodules import sdm_monomial_divides
>>> sdm_monomial_divides((1, 0, 0), (1, 0, 0))
True

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

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

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

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

负面示例：

\(A = f_1\) 不能整除 \(B = f_2\)

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

\(A = x f_1\) 不能整除 \(B = f_1\)

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

\(A = xy^2 f_5\) 不能整除 \(B = y f_5\)

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

sympy.polys.distributedmodules.sdm_LC(f, K)

返回 f 的首项系数。

sympy.polys.distributedmodules.sdm_to_dict(f)

从分布式多项式创建一个字典。

sympy.polys.distributedmodules.sdm_from_dict(d, O)

从字典创建一个sdm。

这里 O 是使用的单项式顺序。

示例

>>> from sympy.polys.distributedmodules import sdm_from_dict
>>> from sympy.polys import QQ, 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)]

sympy.polys.distributedmodules.sdm_add(f, g, O, K)

添加两个模块元素 f, g。

加法是在基域 K 上进行的，单项式根据 O 排序。

示例

所有示例均使用字典序。

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

>>> from sympy.polys.distributedmodules import sdm_add
>>> from sympy.polys import lex, QQ
>>> 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)]

sympy.polys.distributedmodules.sdm_LM(f)

返回 f 的领先单项式。

仅在 \(f e 0\) 时有效。

示例

>>> from sympy.polys.distributedmodules import sdm_LM, sdm_from_dict
>>> from sympy.polys import QQ, 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)

sympy.polys.distributedmodules.sdm_LT(f)

返回 f 的首项。

仅在 \(f e 0\) 时有效。

示例

>>> from sympy.polys.distributedmodules import sdm_LT, sdm_from_dict
>>> from sympy.polys import QQ, 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)

sympy.polys.distributedmodules.sdm_mul_term(f, term, O, K)

将分布式模块元素 f 乘以一个（多项式）项 term。

系数的乘法是在基域 K 上进行的，并且单项式根据 O 进行排序。

示例

\(0 f_1 = 0\)

>>> from sympy.polys.distributedmodules import sdm_mul_term
>>> from sympy.polys import lex, QQ
>>> 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)]

sympy.polys.distributedmodules.sdm_zero()

返回零模块元素。

sympy.polys.distributedmodules.sdm_deg(f)

f 的度数。

这是其所有单项式的次数的最大值。如果 f 为零，则无效。

示例

>>> from sympy.polys.distributedmodules import sdm_deg
>>> sdm_deg([((1, 2, 3), 1), ((10, 0, 1), 1), ((2, 3, 4), 4)])
7

sympy.polys.distributedmodules.sdm_from_vector(vec, O, K, **opts)

从表达式可迭代对象创建一个sdm。

系数在基域 K 中创建，并且项根据单项式顺序 O 排序。命名参数传递给多项式转换代码，可以用来指定例如生成元。

示例

>>> from sympy.polys.distributedmodules import sdm_from_vector
>>> from sympy.abc import x, y, z
>>> from sympy.polys import QQ, lex
>>> 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)]

sympy.polys.distributedmodules.sdm_to_vector(f, gens, K, n=None)

将 sdm f 转换为多项式表达式的列表。

多项式环的生成元通过 gens 指定。模的秩是猜测的，或者通过 n 传递。基域假设为 K。

示例

>>> from sympy.polys.distributedmodules import sdm_to_vector
>>> from sympy.abc import x, y, z
>>> from sympy.polys import QQ
>>> 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]

多项式因式分解算法

欧几里得算法的许多变体：

经典余数序列

设 \(K\) 是一个域，考虑系数在 \(K\) 中的单个不定元 \(X\) 的多项式环 \(K[X]\)。给定 \(K[X]\) 中的两个元素 \(f\) 和 \(g\)，且 \(g\neq 0\)，存在唯一的多项式 \(q\) 和 \(r\)，使得 \(f = qg + r\) 且 \(\deg(r) < \deg(g)\) 或 \(r = 0\)。它们分别记作 `mathrm{quo}(f,g)`（商）和 `mathrm{rem}(f,g)`（余数），因此我们有*除法恒等式*

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

由此可知，\(K[X]\) 的每个理想 \(I\) 都是主理想，由任意一个最小次数的非零元素生成（假设 \(I\) 非零）。事实上，如果 \(g\) 是这样的多项式，而 \(f\) 是 \(I\) 中的任意元素，\(\mathrm{rem}(f,g)\) 作为 \(f\) 和 \(g\) 的线性组合属于 \(I\)，因此必须为零；因此 \(f\) 是 \(g`\) 的倍数。

使用这一结果，可以找到`K[X]`中任意多项式`f,g,ldots`的`最大公约数 <https://en.wikipedia.org/wiki/Greatest_common_divisor>`_（gcd）。如果`I`是由给定多项式在`K[X]`中的所有线性组合形成的理想，且`d`是其生成元，那么这些多项式的每个公约数也整除`d`。另一方面，给定的多项式是生成元`d`的倍数；因此`d`是这些多项式的gcd，记作`mathrm{gcd}(f,g,ldots)`。

现在可以按如下方式获得多项式 \(f\) 和 \(g\) 在 \(K[X]\) 中的最大公约数的算法。根据除法定理，\(r = \mathrm{rem}(f,g)\) 位于由 \(f\) 和 \(g\) 生成的理想中，同样 \(f\) 位于由 \(g\) 和 \(r\) 生成的理想中。因此，由对 \((f,g)\) 和 \((g,r)\) 生成的理想是相同的。设 \(f_0 = f\)，\(f_1 = g\)，并递归定义 \(f_i = \mathrm{rem}(f_{i-2},f_{i-1})\) 对于 \(i\ge 2\)。由于多项式的次数严格递减，递归在有限步后以 \(f_{k+1}=0\) 结束。根据上述注释，所有对 \((f_{i-1},f_i)\) 生成相同的理想。特别是，由 \(f\) 和 \(g\) 生成的理想仅由 \(f_k\) 生成，因为 \(f_{k+1} = 0\)。因此 \(d = f_k\) 是 \(f\) 和 \(g\) 的最大公约数。

多项式序列 \(f_0\), \(f_1,\ldots, f_k\) 被称为由 \((f,g)\) 确定的*欧几里得多项式余数序列*，这是由于它与自然数最大公约数的经典`欧几里得算法 <https://en.wikipedia.org/wiki/Euclidean_algorithm>`_ 之间的类比。

该算法可以通过使用完整的除法恒等式，递归地将每个 \(f_i\) 表示为 \(f\) 和 \(g\) 的线性组合，从而扩展以获得 \(d\) 关于 \(f\) 和 \(g\) 的表达式。这导致了一个方程

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

类似于整数情况下的 贝祖等式。

sympy.polys.euclidtools.dmp_half_gcdex(f, g, u, K)

在 \(F[X]\) 中的半扩展欧几里得算法。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

sympy.polys.euclidtools.dmp_gcdex(f, g, u, K)

在 \(F[X]\) 中的扩展欧几里得算法。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

sympy.polys.euclidtools.dmp_invert(f, g, u, K)

在 \(F[X]\) 中计算 \(f\) 对 \(g\) 的模逆。

示例

>>> from sympy.polys import ring, QQ
>>> R, x = ring("x", QQ)

sympy.polys.euclidtools.dmp_euclidean_prs(f, g, u, K)

欧几里得多项式余数序列 (PRS) 在 \(K[X]\) 中。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

简化余数序列

假设，像通常一样，系数域 \(K\) 是整环 \(A\) 的分数域。在这种情况下，欧几里得余数序列中多项式的系数（分子和分母）往往会增长得非常快。

如果 \(A\) 是一个唯一分解域，系数可以通过消去分子和分母的公因子来简化。进一步的简化是可能的，注意到 \(K[X]\) 中的多项式的最大公约数不是唯一的：它可以乘以任何（非零）常数因子。

任何多项式 \(f\) 在 \(K[X]\) 中都可以通过提取其系数分母和分子公因数来简化。这得到表示 \(f = cF\)，其中 \(c\in K\) 是 \(f\) 的 内容，而 \(F\) 是一个 本原 多项式，即，系数互素的 \(A[X]\) 中的多项式。

可以通过用给定的多项式 \(f\) 和 \(g\) 替换它们的本原部分来启动算法。这只会通过一个常数因子修改 \(\mathrm{rem}(f,g)\)。用其本原部分替换并继续递归，我们得到欧几里得余数序列中所有多项式的本原部分，包括本原的 \(\mathrm{gcd}(f,g)\)。

这个序列是 原始多项式余数序列 。它是 一般多项式余数序列 的一个例子，其中计算的余数通过常数乘数（或除数）进行修改，以简化结果。

sympy.polys.euclidtools.dmp_primitive_prs(f, g, u, K)

\(K[X]\) 中的原始多项式余数序列 (PRS)。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

子结果序列

原始多项式序列的系数不会过度增长，但计算原始部分需要额外的处理努力。此外，该方法仅适用于唯一分解域的分数域，例如，不包括一般的数域。

Collins [Collins67] 意识到，所谓的一对多项式的 子结果多项式 也形成了一个广义余数序列。这些多项式的系数可以表示为给定多项式系数的行列式。因此（它们的大小对数）仅线性增长。此外，如果给定多项式的系数在子域 \(A\) 中，那么子结果多项式的系数也在 \(A\) 中。这意味着子结果序列与原始余数序列相当，而不依赖于 \(A\) 中的唯一因子分解。

要了解子结果式如何与余数序列相关联，请记住序列中的所有多项式 \(h\) 都是给定多项式 \(f\) 和 \(g\) 的线性组合。

\[h = uf + vg\]

在多项式 \(u\) 和 \(v\) 在 \(K[X]\) 中。此外，正如从扩展欧几里得算法中看到的，\(u\) 和 \(v\) 的次数相对较低，每一步的增长有限。

设 \(n = \deg(f)\)，\(m = \deg(g)\)，并假设 \(n\ge m\)。如果 \(\deg(h) = j < m\)，乘积 \(uf\) 和 \(vg\) 中幂 \(X^k\) (\(k > j\)) 的系数会相互抵消。特别地，乘积的次数必须相同，设为 \(l\)。那么 \(\deg(u) = l - n\) 和 \(\deg(v) = l - m\)，总共有 \(2l - n - m + 2\) 个系数需要确定。

另一方面，等式 \(h = uf + vg\) 意味着 \(l - j\) 个系数的线性组合为零，这些系数与幂 \(X^i`（`j < i \leq l\)）相关联，并且有一个给定的非零值，即 \(h\) 的首项系数。

为了满足这些 \(l - j + 1\) 个线性方程，需要确定的系数总数通常不能低于 \(l - j + 1\)。这导致不等式 \(l \ge n + m - j - 1\)。取 \(l = n + m - j - 1\)，我们得到 \(\deg(u) = m - j - 1\) 和 \(\deg(v) = n - j - 1\)。

在 \(j = 0\) 的情况下，所得线性方程组的矩阵是与 \(f\) 和 \(g\) 相关的 Sylvester 矩阵 \(S(f,g)\)，这是一个 \((n+m) \times (n+m)\) 矩阵，其元素为 \(f\) 和 \(g\) 的系数。其行列式是这对 \((f,g)\) 的 结式 \(\mathrm{res}(f,g)\)。当且仅当 \(f\) 和 \(g\) 互质时，它不为零。

对于区间 \(0\) 到 \(m\) 中的任意 \(j\)，线性系统的矩阵是 Sylvester 矩阵的一个 \((n+m-2j) imes (n+m-2j)\) 子矩阵。其行列式 \(s_j(f,g)\) 称为 \(f\) 和 \(g\) 的第 \(j\) 个 标量子结式。

如果 \(s_j(f,g)\) 不为零，相关的方程 \(h = uf + vg\) 有一个唯一解，其中 \(\deg(h) = j\)，并且 \(h\) 的首项系数可以是任意给定值；其中首项系数为 \(s_j(f,g)\) 的解是 \((f,g)\) 对的第 \(j\) 个 子结式多项式，简称 子结式，记作 \(S_j(f,g)\)。这一选择保证了剩余系数也是Sylvester矩阵的某些子行列式。特别是，如果 \(f\) 和 \(g\) 在 \(A[X]\) 中，那么 \(S_j(f,g)\) 也在 \(A[X]\) 中。这种子结式的构造适用于任何 \(j\) 在 \(0\) 到 \(m\) 之间的值，无论 \(s_j(f,g)\) 的值如何；如果它为零，则 \(\deg(S_j(f,g)) < j\)。

子结式的性质如下。设 \(n_0 = \deg(f)\)，\(n_1 = \deg(g)\)，\(n_2, \ldots, n_k\) 为余式序列中多项式的递减次数序列。设 \(0 \le j \le n_1\)；则

• \(s_j(f,g) e 0\) 当且仅当 \(j = n_i\) 对于某些 \(i\)。

• \(S_j(f,g) e 0\) 当且仅当 \(j = n_i\) 或 \(j = n_i - 1\) 对于某些 \(i\)。

通常，对于 \(1 < i \le k\)，有 \(n_{i-1} - n_i = 1\)。如果对于某些 \(i\) 有 \(n_{i-1} - n_i > 1`（即*异常*情况），那么 `S_{n_{i-1}-1}(f,g)\) 和 \(S_{n_i}(f,g)\) 是彼此的常数倍。因此，两者中的任何一个都可以包含在多项式余数序列中。前者由较小的行列式给出，因此预期其系数较小。

Collins 通过设定 次余数序列 来定义了 subresultant remainder sequence。

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

在一般情况下，这些与 \(S_{n_i}(f,g)\) 相同。他还推导了余项公式中常数 \(\gamma_i\) 的表达式。

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

关于 \(f_1,\ldots,f_{i-1}\) 的领先系数，在域 \(K\) 中进行操作。

Brown 和 Traub [BrownTraub71] 后来开发了一种递归程序来计算系数 \(\gamma_i\)。他们的算法仅处理域 \(A\) 的元素（假设 \(f,g\in A[X]\)）。然而，在异常情况下存在一个问题，即在 \(A\) 中的除法只能被推测为精确的。

这一结论随后由布朗 [Brown78] 证实，他指出除法的结果实际上是一个标量子结果。更具体地说，在计算 \(f_i\) 时出现的常数是 \(s_{n_{i-2}}(f,g)`（定理 3）。这一发现的意义在于，标量子结果作为算法的副产品被计算出来，除了 `s_{n_k}(f,g)\) 在找到 \(f_{k+1} = 0\) 后不再需要。完成最后一步，我们得到了所有非零的标量子结果，包括最后一个，如果它不消失，则是结果。

sympy.polys.euclidtools.dmp_inner_subresultants(f, g, u, K)

在 \(K[X]\) 中的子结式 PRS 算法。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_subresultants(f, g, u, K)

计算多项式 \(K[X]\) 中的两个多项式的子结果PRS。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_prs_resultant(f, g, u, K)

在 \(K[X]\) 中使用子结式PRS的结果算法。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_zz_modular_resultant(f, g, p, u, K)

计算 \(f\) 和 \(g\) 在素数 \(p\) 模下的结果。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_zz_collins_resultant(f, g, u, K)

Collins 在 \(Z[X]\) 中的模块化结果算法。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_qq_collins_resultant(f, g, u, K0)

Collins 在 \(Q[X]\) 中的模块化结果算法。

示例

>>> from sympy.polys import ring, QQ
>>> R, x,y = ring("x,y", QQ)

>>> f = QQ(1,2)*x + 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

sympy.polys.euclidtools.dmp_resultant(f, g, u, K, includePRS=False)

计算 \(K[X]\) 中两个多项式的结果。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_discriminant(f, u, K)

计算多项式 \(K[X]\) 的判别式。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_rr_prs_gcd(f, g, u, K)

在环上使用子结式计算多项式GCD。

返回 (h, cff, cfg) 使得 a = gcd(f, g)， cff = quo(f, h)， 和 cfg = quo(g, h)。

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

sympy.polys.euclidtools.dmp_ff_prs_gcd(f, g, u, K)

使用子结式在域上计算多项式最大公约数。

返回 (h, cff, cfg) 使得 a = gcd(f, g)， cff = quo(f, h)， 和 cfg = quo(g, h)。

示例

>>> from sympy.polys import ring, QQ
>>> R, x,y, = ring("x,y", QQ)

>>> f = QQ(1,2)*x**2 + x*y + QQ(1,2)*y**2
>>> g = x**2 + x*y

>>> R.dmp_ff_prs_gcd(f, g)
(x + y, 1/2*x + 1/2*y, x)

sympy.polys.euclidtools.dmp_zz_heu_gcd(f, g, u, K)

在 \(Z[X]\) 中的启发式多项式最大公约数。

给定单变量多项式 \(f\) 和 \(g\) 在 \(Z[X]\) 中，返回它们的 GCD 和余因子，即多项式 h、cff 和 cfg，使得:

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

该算法完全是启发式的，这意味着它可能无法计算最大公约数。这将通过引发异常来表示。在这种情况下，您需要切换到另一种最大公约数方法。

该算法通过在某些点处计算多项式 f 和 g 的值，并计算这些评估值的（快速）整数 GCD 来计算多项式 GCD。多项式 GCD 通过插值从整数图像中恢复。评估过程将 f 和 g 逐变量减少为一个大整数。最后一步是验证插值多项式是否为正确的 GCD。这作为副作用给出了输入多项式的辅因子。

参考文献

[1]

[Liao95]

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

sympy.polys.euclidtools.dmp_qq_heu_gcd(f, g, u, K0)

在 \(Q[X]\) 中的启发式多项式最大公约数。

返回 (h, cff, cfg) 使得 a = gcd(f, g)， cff = quo(f, h)， 和 cfg = quo(g, h)。

示例

>>> from sympy.polys import ring, QQ
>>> R, x,y, = ring("x,y", QQ)

>>> f = QQ(1,4)*x**2 + x*y + y**2
>>> g = QQ(1,2)*x**2 + x*y

>>> R.dmp_qq_heu_gcd(f, g)
(x + 2*y, 1/4*x + 1/2*y, 1/2*x)

sympy.polys.euclidtools.dmp_inner_gcd(f, g, u, K)

在 \(K[X]\) 中计算多项式 \(f\) 和 \(g\) 的最大公约数和余因子。

返回 (h, cff, cfg) 使得 a = gcd(f, g)， cff = quo(f, h)， 和 cfg = quo(g, h)。

示例

>>> from sympy.polys import ring, ZZ
>>> 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)

sympy.polys.euclidtools.dmp_gcd(f, g, u, K)

在 \(K[X]\) 中计算多项式 \(f\) 和 \(g\) 的最大公约数。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_lcm(f, g, u, K)

在 \(K[X]\) 中计算多项式 \(f\) 和 \(g\) 的最小公倍数。

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.euclidtools.dmp_content(f, u, K)

返回多元系数的最大公约数。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

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

sympy.polys.euclidtools.dmp_primitive(f, u, K)

返回多元内容和一个原始多项式。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y, = ring("x,y", ZZ)

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

sympy.polys.euclidtools.dmp_cancel(f, g, u, K, include=True)

在有理函数 \(f/g\) 中消去公因子。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

特征为零的多项式分解：

sympy.polys.factortools.dup_trial_division(f, factors, K)

使用试除法确定单变量多项式的因子的重数。

如果任何因子不能整除 f，将会引发错误。

sympy.polys.factortools.dmp_trial_division(f, factors, u, K)

使用试除法确定多元多项式的因子的重数。

如果任何因子不能整除 f，将会引发错误。

sympy.polys.factortools.dup_zz_mignotte_bound(f, K)

Knuth-Cohen 变体的 Mignotte 界，用于 K[x] 中的单变量多项式。

参考文献

..[1] [Abbott13]

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> f = x**3 + 14*x**2 + 56*x + 64
>>> R.dup_zz_mignotte_bound(f)
152

通过检查 factor(f) 我们可以看到最大系数是 8

还考虑一个情况，例如 f = 2*x**2 + 3*x + 4 ，f 是不可约的。为了避免这些情况的错误，我们返回边界加上 f 的最大系数。

>>> f = 2*x**2 + 3*x + 4
>>> R.dup_zz_mignotte_bound(f)
6

最后，为了比较新旧 Mignotte 界限之间的差异，请考虑不可约多项式：

>>> f = 87*x**7 + 4*x**6 + 80*x**5 + 17*x**4 + 9*x**3 + 12*x**2 + 49*x + 26
>>> R.dup_zz_mignotte_bound(f)
744

新的 Mignotte 界限是 744，而旧的（SymPy 1.5.1）是 1937664。

sympy.polys.factortools.dmp_zz_mignotte_bound(f, u, K)

多项式在 \(K[X]\) 中的多元多项式的 Mignotte 界。

sympy.polys.factortools.dup_zz_hensel_step(m, f, g, h, s, t, K)

在 \(Z[x]\) 中的 Hensel 提升的一个步骤。

给定正整数 \(m\) 和 \(Z[x]\) 多项式 \(f\), \(g\), \(h\), \(s\) 和 \(t\)，使得:

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)

返回多项式 \(G\), \(H\), \(S\) 和 \(T\)，使得:

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

参考文献

[1]

[Gathen99]

sympy.polys.factortools.dup_zz_hensel_lift(p, f, f_list, l, K)

在 \(Z[x]\) 中的多因子 Hensel 提升。

给定一个素数 \(p\)，多项式 \(f\) 在 \(Z[x]\) 上，使得 \(lc(f)\) 是模 \(p\) 的单位，单项对互质多项式 \(f_i\) 在 \(Z[x]\) 上满足:

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

并给定一个正整数 \(l\)，返回一组首一多项式 \(F_1, F_2, \dots, F_r\) 满足:

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

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

参考文献

[1]

[Gathen99]

sympy.polys.factortools.dup_zz_zassenhaus(f, K)

在 \(Z[x]\) 中分解原始的、无平方因子的多项式。

sympy.polys.factortools.dup_zz_irreducible_p(f, K)

使用Eisenstein准则测试不可约性。

sympy.polys.factortools.dup_cyclotomic_p(f, K, irreducible=False)

高效地测试 f 是否为分圆多项式。

参考文献

布拉德福德, 拉塞尔 J., 和 詹姆斯 H. 达文波特. “环状多项式的有效测试.” 在 国际符号与代数计算研讨会, pp. 244-251. 斯普林格, 柏林, 海德堡, 1988.

示例

>>> from sympy.polys import ring, ZZ
>>> 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

sympy.polys.factortools.dup_zz_cyclotomic_poly(n, K)

高效生成第 n 个分圆多项式。

sympy.polys.factortools.dup_zz_cyclotomic_factor(f, K)

在 \(Z[x]\) 中高效地分解多项式 \(x**n - 1\) 和 \(x**n + 1\)。

给定一个单变量多项式 \(f\) 在 \(Z[x]\) 中，返回 \(f\) 的因子列表，前提是 \(f\) 的形式为 \(x**n - 1\) 或 \(x**n + 1\) 且 \(n >= 1\)。否则返回 None。

因式分解是通过对 \(f\) 进行分圆分解来实现的，这使得这种方法比任何其他直接因式分解方法（例如 Zassenhaus 的方法）快得多。

参考文献

[1]

[Weisstein09]

sympy.polys.factortools.dup_zz_factor_sqf(f, K)

在 \(Z[x]\) 中分解无平方（非本原）多项式。

sympy.polys.factortools.dup_zz_factor(f, K)

在 \(Z[x]\) 中分解（非无平方因子）多项式。

给定一个单变量多项式 \(f\) 在 \(Z[x]\) 中，计算其在整数上的不可约因子的完全分解 \(f_1, ..., f_n\):

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

因式分解是通过将输入多项式简化为一个原始的无平方多项式，并使用Zassenhaus算法对其进行分解来计算的。试验除法用于恢复因子的重数。

结果以一个元组的形式返回，包含:

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

参考文献

[1]

[Gathen99]

示例

考虑多项式 \(f = 2*x**4 - 2\):

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_zz_factor(2*x**4 - 2)
(2, [(x - 1, 1), (x + 1, 1), (x**2 + 1, 1)])

结果我们得到了以下因式分解:

f = 2 (x - 1) (x + 1) (x**2 + 1)

请注意，这是一个对整数的完全因式分解，然而在复整数上，我们可以对最后一项进行因式分解。

默认情况下，多项式 \(x**n - 1\) 和 \(x**n + 1\) 使用分圆分解进行因式分解以加速计算。要禁用此行为，请设置 cyclotomic=False。

sympy.polys.factortools.dmp_zz_wang_non_divisors(E, cs, ct, K)

Wang/EEZ: 计算一组有效的除数。

sympy.polys.factortools.dmp_zz_wang_test_points(f, T, ct, A, u, K)

Wang/EEZ: 测试评估点的适用性。

sympy.polys.factortools.dmp_zz_wang_lead_coeffs(f, T, cs, E, H, A, u, K)

Wang/EEZ: 计算正确的首项系数。

sympy.polys.factortools.dup_zz_diophantine(F, m, p, K)

Wang/EEZ: 求解一元丢番图方程。

sympy.polys.factortools.dmp_zz_diophantine(F, c, A, d, p, u, K)

Wang/EEZ: 解决多元丢番图方程。

sympy.polys.factortools.dmp_zz_wang_hensel_lifting(f, H, LC, A, p, u, K)

Wang/EEZ: 并行Hensel提升算法。

sympy.polys.factortools.dmp_zz_wang(f, u, K, mod=None, seed=None)

在 \(Z[X]\) 中分解原始的无平方多项式。

给定一个在 \(Z[x_1,...,x_n]\) 中的多元多项式 \(f\)，它在 \(x_1\) 中是原始且无平方因子的，计算 \(f\) 在整数上的不可约因式分解。

该过程基于 Wang 的增强扩展 Zassenhaus 算法。该算法通过将 \(f\) 视为 \(Z[x_2,...,x_n][x_1]\) 中的单变量多项式来工作，为此计算了一个求值映射:

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

其中 \(a_i\)，对于 \(i = 2, \dots, n\)，是精心选择的整数。该映射用于将 \(f\) 转换为 \(Z[x_1]\) 中的单变量多项式，可以使用 Zassenhaus 算法高效地进行因式分解。最后一步是通过提升单变量因子来获得真正的多变量因子。为此，使用了并行的 Hensel 提升过程。

参数 seed 传递给 _randint 并且可以用于种子化 randint（当为整数时）或者（出于测试目的）可以是一个数字序列。

参考文献

[1]

[Wang78]

[2]

[Geddes92]

sympy.polys.factortools.dmp_zz_factor(f, u, K)

在 \(Z[X]\) 中分解（非无平方因子）多项式。

给定一个多项式 \(f\) 在 \(Z[x]\) 中，计算其完全因式分解 \(f_1, \dots, f_n\) 为整数上的不可约多项式:

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

因式分解是通过将输入多项式简化为一个原始的无平方多项式，并使用增强的扩展Zassenhaus（EEZ）算法对其进行分解来计算的。试除法用于恢复因子的重数。

结果以一个元组的形式返回，包含:

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

考虑多项式 \(f = 2*(x**2 - y**2)\):

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

结果我们得到了以下因式分解:

f = 2 (x - y) (x + y)

参考文献

[1]

[Gathen99]

sympy.polys.factortools.dup_qq_i_factor(f, K0)

在 \(QQ_I[x]\) 中将单变量多项式分解为不可约因子。

sympy.polys.factortools.dup_zz_i_factor(f, K0)

在 \(ZZ_I[x]\) 中将单变量多项式分解为不可约因子。

sympy.polys.factortools.dmp_qq_i_factor(f, u, K0)

在 \(QQ_I[X]\) 中将多元多项式分解为不可约因子。

sympy.polys.factortools.dmp_zz_i_factor(f, u, K0)

在 \(ZZ_I[X]\) 中将多元多项式分解为不可约因子。

sympy.polys.factortools.dup_ext_factor(f, K)

在代数数域上分解单变量多项式。

域 \(K\) 必须是一个代数数域 \(k(a)\) （参见 QQ<a>）。

参见

dmp_ext_factor

k(a) 上多元多项式的类似函数。

dup_sqf_norm

子程序 sqfr_norm 同样来自 [Trager76]。

sympy.polys.polytools.factor

最终根据需要使用此函数的高级函数。

示例

首先定义代数数域 \(K = \mathbb{Q}(\sqrt{2})\)：

>>> from sympy import QQ, sqrt
>>> from sympy.polys.factortools import dup_ext_factor
>>> K = QQ.algebraic_field(sqrt(2))

我们现在可以在 \(K\) 上对多项式 \(x^2 - 2\) 进行因式分解：

>>> p = [K(1), K(0), K(-2)] # x^2 - 2
>>> p1 = [K(1), -K.unit]    # x - sqrt(2)
>>> p2 = [K(1), +K.unit]    # x + sqrt(2)
>>> dup_ext_factor(p, K) == (K.one, [(p1, 1), (p2, 1)])
True

通常这会在更高层次上完成：

>>> from sympy import factor
>>> from sympy.abc import x
>>> factor(x**2 - 2, extension=sqrt(2))
(x - sqrt(2))*(x + sqrt(2))

sympy.polys.factortools.dmp_ext_factor(f, u, K)

在代数数域上分解多元多项式。

域 \(K\) 必须是一个代数数域 \(k(a)\) （参见 QQ<a>）。

参见

dup_ext_factor

k(a) 上的一元多项式的类似函数。

dmp_sqf_norm

来自 [Trager76] 的子程序 sqfr_norm 的多变量版本

sympy.polys.polytools.factor

最终根据需要使用此函数的高级函数。

示例

首先定义代数数域 \(K = \mathbb{Q}(\sqrt{2})\)：

>>> from sympy import QQ, sqrt
>>> from sympy.polys.factortools import dmp_ext_factor
>>> K = QQ.algebraic_field(sqrt(2))

我们现在可以在 \(K\) 上对多项式 \(x^2 y^2 - 2\) 进行因式分解：

>>> p = [[K(1),K(0),K(0)], [], [K(-2)]] # x**2*y**2 - 2
>>> p1 = [[K(1),K(0)], [-K.unit]]       # x*y - sqrt(2)
>>> p2 = [[K(1),K(0)], [+K.unit]]       # x*y + sqrt(2)
>>> dmp_ext_factor(p, 1, K) == (K.one, [(p1, 1), (p2, 1)])
True

通常这会在更高层次上完成：

>>> from sympy import factor
>>> from sympy.abc import x, y
>>> factor(x**2*y**2 - 2, extension=sqrt(2))
(x*y - sqrt(2))*(x*y + sqrt(2))

sympy.polys.factortools.dup_gf_factor(f, K)

在有限域上分解单变量多项式。

sympy.polys.factortools.dmp_gf_factor(f, u, K)

在有限域上分解多元多项式。

sympy.polys.factortools.dup_factor_list(f, K0)

在 \(K[x]\) 中将单变量多项式分解为不可约因子。

sympy.polys.factortools.dup_factor_list_include(f, K)

在 \(K[x]\) 中将单变量多项式分解为不可约因子。

sympy.polys.factortools.dmp_factor_list(f, u, K0)

在 \(K[X]\) 中将多元多项式分解为不可约因子。

sympy.polys.factortools.dmp_factor_list_include(f, u, K)

在 \(K[X]\) 中将多元多项式分解为不可约因子。

sympy.polys.factortools.dup_irreducible_p(f, K)

如果单变量多项式 f 在其定义域上没有因子，则返回 True。

sympy.polys.factortools.dmp_irreducible_p(f, u, K)

如果多元多项式 f 在其定义域上没有因子，则返回 True。

无平方因子分解：

sympy.polys.sqfreetools.dup_sqf_p(f, K)

如果 f 是 K[x] 中的无平方多项式，则返回 True。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_sqf_p(x**2 - 2*x + 1)
False
>>> R.dup_sqf_p(x**2 - 1)
True

sympy.polys.sqfreetools.dmp_sqf_p(f, u, K)

如果 f 是 K[X] 中的无平方多项式，则返回 True。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.sqfreetools.dup_sqf_norm(f, K)

在 \(K[x]\) 中找到一个 \(f\) 的移位，使其范数为无平方因子。

域 \(K\) 必须是一个代数数域 \(k(a)\) （参见 QQ<a>）。

返回 \((s,g,r)\)，使得 \(g(x)=f(x-sa)\)，\(r(x)=\text{Norm}(g(x))\) 并且 \(r\) 是 \(k\) 上的无平方多项式。

参见

dmp_sqf_norm

k(a) 上多元多项式的类似函数。

dmp_norm

直接计算 \(f\) 的范数，不进行任何偏移。

dup_ext_factor

实现使用此算法的Trager算法的函数。

sympy.polys.polytools.sqf_norm

使用此功能的高级接口。

示例

我们首先创建代数数域 \(K=k(a)=\mathbb{Q}(\sqrt{3})\) 和环 \(K[x]\) 以及 \(k[x]\)：

>>> from sympy.polys import ring, QQ
>>> from sympy import sqrt

>>> K = QQ.algebraic_field(sqrt(3))
>>> R, x = ring("x", K)
>>> _, X = ring("x", QQ)

我们现在可以为 \(f\) 的移位找到一个无平方范数：

>>> f = x**2 - 1
>>> s, g, r = R.dup_sqf_norm(f)

移位 \(s\) 的选择是任意的，而 \(g\) 和 \(r\) 返回的特定值由 \(s\) 决定。

>>> s == 1
True
>>> g == x**2 - 2*sqrt(3)*x + 2
True
>>> r == X**4 - 8*X**2 + 4
True

不变量是：

>>> g == f.shift(-s*K.unit)
True
>>> g.norm() == r
True
>>> r.is_squarefree
True

sympy.polys.sqfreetools.dmp_sqf_norm(f, u, K)

在 K[X] 中找到一个 f 的移位，使其范数为无平方因子。

域 \(K\) 必须是一个代数数域 \(k(a)\) （参见 QQ<a>）。

返回 \((s,g,r)\)，使得 \(g(x_1,x_2,\cdots)=f(x_1-s_1 a, x_2 - s_2 a, \cdots)\)，\(r(x)=\text{范数}(g(x))\) 且 \(r\) 是 \(k\) 上的无平方因子多项式。

参见

dup_sqf_norm

k(a) 上的一元多项式的类似函数。

dmp_norm

直接计算 \(f\) 的范数，不进行任何偏移。

dmp_ext_factor

实现使用此算法的Trager算法的函数。

sympy.polys.polytools.sqf_norm

使用此功能的高级接口。

示例

我们首先创建代数数域 \(K=k(a)=\mathbb{Q}(i)\) 和环 \(K[x,y]\) 以及 \(k[x,y]\)：

>>> from sympy.polys import ring, QQ
>>> from sympy import I

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

我们现在可以为 \(f\) 的移位找到一个无平方范数：

>>> f = x*y + y**2
>>> s, g, r = R.dmp_sqf_norm(f)

移位 s 的选择是任意的，而 g 和 r 返回的特定值由 s 决定。

>>> s
[0, 1]
>>> g == x*y - I*x + y**2 - 2*I*y - 1
True
>>> r == X**2*Y**2 + X**2 + 2*X*Y**3 + 2*X*Y + Y**4 + 2*Y**2 + 1
True

所需的恒定条件是：

>>> g == f.shift_list([-si*K.unit for si in s])
True
>>> g.norm() == r
True
>>> r.is_squarefree
True

sympy.polys.sqfreetools.dmp_norm(f, u, K)

K[X] 中 f 的范数，通常不是无平方的。

域 \(K\) 必须是一个代数数域 \(k(a)\) （参见 QQ<a>）。

参见

dmp_sqf_norm

计算 \(f\) 的移位，使得 \(\text{Norm}(f)\) 是无平方因子的。

sympy.polys.polytools.Poly.norm

调用此函数的更高层次函数。

示例

我们首先定义代数数域 \(K = k(a) = \mathbb{Q}(\sqrt{2})\)：

>>> from sympy import QQ, sqrt
>>> from sympy.polys.sqfreetools import dmp_norm
>>> k = QQ
>>> K = k.algebraic_field(sqrt(2))

我们现在可以计算多项式 \(p\) 在 \(K[x,y]\) 中的范数：

>>> p = [[K(1)], [K(1),K.unit]]                  # x + y + sqrt(2)
>>> N = [[k(1)], [k(2),k(0)], [k(1),k(0),k(-2)]] # x**2 + 2*x*y + y**2 - 2
>>> dmp_norm(p, 1, K) == N
True

在更高层次的函数中，即：

>>> from sympy import expand, roots, minpoly
>>> from sympy.abc import x, y
>>> from math import prod
>>> a = sqrt(2)
>>> e = (x + y + a)
>>> e.as_poly([x, y], extension=a).norm()
Poly(x**2 + 2*x*y + y**2 - 2, x, y, domain='QQ')

这等于表达式 \(x + y + a_i\) 的乘积，其中 \(a_i\) 是 \(a\) 的共轭：

>>> pa = minpoly(a)
>>> pa
_x**2 - 2
>>> rs = roots(pa, multiple=True)
>>> rs
[sqrt(2), -sqrt(2)]
>>> n = prod(e.subs(a, r) for r in rs)
>>> n
(x + y - sqrt(2))*(x + y + sqrt(2))
>>> expand(n)
x**2 + 2*x*y + y**2 - 2

sympy.polys.sqfreetools.dup_gf_sqf_part(f, K)

在 GF(p)[x] 中计算 f 的无平方部分。

sympy.polys.sqfreetools.dmp_gf_sqf_part(f, u, K)

在 GF(p)[X] 中计算 f 的无平方部分。

sympy.polys.sqfreetools.dup_sqf_part(f, K)

返回多项式在 K[x] 中的无平方部分。

参见

sympy.polys.polytools.Poly.sqf_part

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> R.dup_sqf_part(x**3 - 3*x - 2)
x**2 - x - 2

sympy.polys.sqfreetools.dmp_sqf_part(f, u, K)

返回多项式在 K[X] 中的无平方部分。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

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

sympy.polys.sqfreetools.dup_gf_sqf_list(f, K, all=False)

在 GF(p)[x] 中计算 f 的无平方分解。

sympy.polys.sqfreetools.dmp_gf_sqf_list(f, u, K, all=False)

在 GF(p)[X] 中计算 f 的无平方分解。

sympy.polys.sqfreetools.dup_sqf_list(f, K, all=False)

返回多项式在 K[x] 中的无平方分解。

使用 [Yun76] 中的 Yun 算法。

参见

dmp_sqf_list

多元多项式的对应函数。

sympy.polys.polytools.sqf_list

用于表达式无平方因式分解的高级函数。

sympy.polys.polytools.Poly.sqf_list

在 Poly 上的类似方法。

参考文献

[Yun76]

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16

>>> R.dup_sqf_list(f)
(2, [(x + 1, 2), (x + 2, 3)])
>>> R.dup_sqf_list(f, all=True)
(2, [(1, 1), (x + 1, 2), (x + 2, 3)])

sympy.polys.sqfreetools.dup_sqf_list_include(f, K, all=False)

返回多项式在 K[x] 中的无平方分解。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

>>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16

>>> R.dup_sqf_list_include(f)
[(2, 1), (x + 1, 2), (x + 2, 3)]
>>> R.dup_sqf_list_include(f, all=True)
[(2, 1), (x + 1, 2), (x + 2, 3)]

sympy.polys.sqfreetools.dmp_sqf_list(f, u, K, all=False)

返回多项式在 \(K[X]\) 中的无平方分解。

参见

dup_sqf_list

单变量多项式的对应函数。

sympy.polys.polytools.sqf_list

用于表达式无平方因式分解的高级函数。

sympy.polys.polytools.Poly.sqf_list

在 Poly 上的类似方法。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x**5 + 2*x**4*y + x**3*y**2

>>> R.dmp_sqf_list(f)
(1, [(x + y, 2), (x, 3)])
>>> R.dmp_sqf_list(f, all=True)
(1, [(1, 1), (x + y, 2), (x, 3)])

sympy.polys.sqfreetools.dmp_sqf_list_include(f, u, K, all=False)

返回多项式在 K[x] 中的无平方分解。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

>>> f = x**5 + 2*x**4*y + x**3*y**2

>>> R.dmp_sqf_list_include(f)
[(1, 1), (x + y, 2), (x, 3)]
>>> R.dmp_sqf_list_include(f, all=True)
[(1, 1), (x + y, 2), (x, 3)]

sympy.polys.sqfreetools.dup_gff_list(f, K)

在 K[x] 中计算 f 的最大阶乘分解。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x = ring("x", ZZ)

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

sympy.polys.sqfreetools.dmp_gff_list(f, u, K)

在 K[X] 中计算 f 的最大阶乘分解。

示例

>>> from sympy.polys import ring, ZZ
>>> R, x,y = ring("x,y", ZZ)

Groebner 基算法

Groebner 基可以用来解决计算交换代数中的许多问题。它们的计算相当复杂，并且对性能非常敏感。我们在这里提供了各种 Groebner 基计算算法的低级实现；请参阅手册的前一节以了解用法。

sympy.polys.groebnertools.groebner(seq, ring, method=None)

计算多项式集合在 \(K[X]\) 中的 Groebner 基。

围绕（默认）改进的 Buchberger 和其他计算 Groebner 基的算法进行封装。可以通过 method 参数或 sympy.polys.polyconfig.setup() 更改算法选择，其中 method 可以是 buchberger 或 f5b。

sympy.polys.groebnertools.spoly(p1, p2, ring)

计算 LCM(LM(p1), LM(p2))/LM(p1)*p1 - LCM(LM(p1), LM(p2))/LM(p2)*p2 这是 S-poly，前提是 p1 和 p2 是首一多项式

sympy.polys.groebnertools.red_groebner(G, ring)

计算约化的Groebner基，来自BeckerWeispfenning93，第216页

选择生成器的一个子集，这些生成器已经生成了理想，并为其计算一个简化的Groebner基。

sympy.polys.groebnertools.is_groebner(G, ring)

检查 G 是否为 Groebner 基。

sympy.polys.groebnertools.is_minimal(G, ring)

检查 G 是否为最小 Groebner 基。

sympy.polys.groebnertools.is_reduced(G, ring)

检查 G 是否为约化 Groebner 基。

sympy.polys.fglmtools.matrix_fglm(F, ring, O_to)

将零维理想的约化Groebner基 F 相对于 O_from 转换为相对于 O_to 的约化Groebner基。

参考文献

[1]

J.C. Faugere, P. Gianni, D. Lazard, T. Mora (1994). 通过改变排序的高效零维Groebner基计算

还提供了用于模的 Groebner 基算法：

sympy.polys.distributedmodules.sdm_spoly(f, g, O, K, phantom=None)

计算 f 和 g 的广义 s-多项式。

假设基域为 K，并且单项式按照 O 排序。

如果 f 或 g 中的任何一个为零，则这是无效的。

如果 \(f\) 和 \(g\) 的首项涉及 \(F\) 的不同基元素，则它们的 s-多项式定义为零。否则，它是 \(f\) 和 \(g\) 的某种线性组合，其中首项相互抵消。详见 [SCA, 定义 2.3.6]。

如果 phantom 不是 None，它应该是一对模块元素，对其执行与 f 和 g 相同的操作。在这种情况下，两个结果都会返回。

示例

>>> from sympy.polys.distributedmodules import sdm_spoly
>>> from sympy.polys import QQ, 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)]

sympy.polys.distributedmodules.sdm_ecart(f)

计算 f 的偏差。

这被定义为 \(f\) 的总次数与 \(f\) 的首项的总次数之差 [SCA, 定义 2.3.7]。

如果 f 为零则无效。

示例

>>> from sympy.polys.distributedmodules import sdm_ecart
>>> sdm_ecart([((1, 2, 3), 1), ((1, 0, 1), 1)])
0
>>> sdm_ecart([((2, 2, 1), 1), ((1, 5, 1), 1)])
3

sympy.polys.distributedmodules.sdm_nf_mora(f, G, O, K, phantom=None)

计算 f 相对于 G 和顺序 O 的弱范式。

假设基域为 K，并且单项式按照 O 排序。

弱范式在 [SCA, 定义 2.3.3] 中定义。它们不是唯一的。这个函数根据 \(G\) 的顺序确定性地计算一个弱范式。

弱正则形式最重要的性质如下：如果 \(R\) 是与单项式排序相关的环（如果排序是全局的，我们只需 \(R = K[x_1, \ldots, x_n]\)，否则它是其某种局部化），\(I\) 是 \(R\) 的任意理想，\(G\) 是 \(I\) 的标准基，那么对于任意 \(f \in R\)，我们有 \(f \in I\) 当且仅当 \(NF(f | G) = 0\)。

这是用于计算关于任意单项式顺序的弱范式的广义Mora算法 [SCA, 算法 2.3.9]。

如果 phantom 不是 None ，它应该是一对“幻影”参数，对其执行与 f 、 G 相同的计算，然后返回两个结果。

sympy.polys.distributedmodules.sdm_groebner(G, NF, O, K, extended=False)

计算 G 相对于顺序 O 的最小标准基。

该算法使用了一种标准形式 NF，例如 sdm_nf_mora。假设基域为 K，并且根据 O 对单项式进行排序。

设 \(N\) 表示由 \(G\) 的元素生成的子模块。\(N\) 的标准基是 \(N\) 的一个子集 \(S\)，使得 \(in(S) = in(N)\)，其中对于 \(F\) 的任何子集 \(X\)，\(in(X)\) 表示由 \(X\) 的元素的初始形式生成的子模块。[SCA, defn 2.3.2]

如果一个标准基的任何子集都不是标准基，则称其为最小标准基。

可以证明标准基总是生成集。

最小标准基不是唯一的。该算法根据 \(G\) 的特定顺序计算确定性结果。

如果 extended=True，还会计算从初始生成元到 Groebner 基的转移矩阵。也就是说，返回一个系数向量列表，表示 Groebner 基的元素在 G 的元素中的表达式。

此函数实现了“糖”策略，参见

Giovini 等人：“请给我一块方糖” 或 Buchberger 算法中的选择策略。

选项

用于 Poly 的选项管理器和公共 API 函数。

class sympy.polys.polyoptions.Options(gens, args, flags=None, strict=False)

多项式操作模块的选项管理器。

属性:

全部

参数

自动

复合

领域

展开

扩展

字段

标志

正式

frac

高斯

生成

生成

贪婪

包含

方法

模数

选项

顺序

多边形

系列

排序

分割

严格

符号

对称

wrt

方法

clear()
clone([updates])	克隆 self 并更新指定的选项。
copy()
fromkeys(iterable[, value])	使用可迭代对象中的键创建一个新字典，并将值设置为指定的值。
get(key[, default])	如果字典中存在键，则返回键的值，否则返回默认值。
items()
keys()
pop(key[, default])	如果未找到键，则返回给定的默认值；否则，引发 KeyError。
popitem(/)	移除并返回一个 (键, 值) 对作为 2-tuple。
setdefault(key[, default])	如果字典中不存在键，则插入键并赋予默认值。
update([E, ]**F)	如果 E 存在且有 .keys() 方法，则执行： for k in E: D[k] = E[k] 如果 E 存在但没有 .keys() 方法，则执行： for k, v in E: D[k] = v 在任何一种情况下，之后都会执行： for k in F: D[k] = F[k]
values()

示例

>>> from sympy.polys.polyoptions import Options
>>> from sympy.polys.polyoptions import build_options

>>> from sympy.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)}

选项

• Expand — 布尔选项

• Gens — 选项

• Wrt — 选项

• 排序 — 选项

• 顺序 — 选项

• 字段 — 布尔选项

• Greedy — 布尔选项

• 域 — 选项

• Split — 布尔选项

• Gaussian — 布尔选项

• 扩展 — 选项

• 模数 — 选项

• Symmetric — 布尔选项

• Strict — 布尔选项

标志

• Auto — 布尔标志

• Frac — 布尔标志

• 正式 — 布尔标志

• Polys — 布尔标志

• Include — 布尔标志

• 全部 — 布尔标志

• Gen — 标志

• Series — 布尔标志

clone(updates={})

克隆 self 并更新指定的选项。

sympy.polys.polyoptions.build_options(gens, args=None)

从关键字参数或…选项构建选项。

配置

用于多项式操作算法的配置工具。

sympy.polys.polyconfig.setup(key, value=None)

为（或重置）配置项赋值。

异常

这些是由多项式模块定义的异常。

TODO 排序并解释

class sympy.polys.polyerrors.BasePolynomialError

多项式相关异常的基类。

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.ExactQuotientFailed(f, g, dom=None)

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.OperationNotSupported(poly, func)

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.HeuristicGCDFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.HomomorphismFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.IsomorphismFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.ExtraneousFactors

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.EvaluationFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.RefinementFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.CoercionFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.NotInvertible

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.NotReversible

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.NotAlgebraic

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.DomainError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.PolynomialError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.UnificationFailed

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.GeneratorsNeeded

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.ComputationFailed(func, nargs, exc)

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.GeneratorsError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.UnivariatePolynomialError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.MultivariatePolynomialError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.PolificationFailed(opt, origs, exprs, seq=False)

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.OptionError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

class sympy.polys.polyerrors.FlagError

属性:

参数

方法

with_traceback

Exception.with_traceback(tb) -- 将 self.__traceback__ 设置为 tb 并返回 self。

新

参考

模块化 GCD

sympy.polys.modulargcd.modgcd_univariate(f, g)

使用模算法计算 \(\mathbb{Z}[x]\) 中两个多项式的最大公约数。

该算法通过计算适合的素数 \(p\) 在 \(\mathbb{Z}_p[x]\) 中的两个单变量整系数多项式 \(f\) 和 \(g\) 的最大公约数，然后利用中国剩余定理重构系数来计算最大公约数。仅对非常可能是所需最大公约数的候选者进行试除。

参数:

fPolyElement

单变量整系数多项式

gPolyElement

单变量整系数多项式

返回:

hPolyElement

多项式 \(f\) 和 \(g\) 的最大公约数

cffPolyElement

\(f\) 的辅因子，即 \(\frac{f}{h}\)

cfgPolyElement

\(g\) 的辅因子，即 \(\frac{g}{h}\)

参考文献

1. [Monagan00]

示例

>>> from sympy.polys.modulargcd import modgcd_univariate
>>> from sympy.polys import ring, ZZ

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

sympy.polys.modulargcd.modgcd_bivariate(f, g)

使用模算法计算 \(\mathbb{Z}[x, y]\) 中两个多项式的最大公约数。

该算法通过计算适合的素数 \(p\) 在 \(\mathbb{Z}_p[x, y]\) 中的 GCD，然后利用中国剩余定理重构系数，来计算两个二元整系数多项式 \(f\) 和 \(g\) 的 GCD。为了在 \(\mathbb{Z}_p\) 上计算二元 GCD，多项式 \(f \; \mathrm{mod} \, p\) 和 \(g \; \mathrm{mod} \, p\) 在某些 \(a \in \mathbb{Z}_p\) 处对 \(y = a\) 进行求值，然后计算它们在 \(\mathbb{Z}_p[x]\) 中的一元 GCD。通过插值这些结果，得到 \(\mathbb{Z}_p[x, y]\) 中的二元 GCD。为了在 \(\mathbb{Z}[x, y]\) 中验证结果，进行试除法，但仅针对非常可能是所需 GCD 的候选者。

参数:

fPolyElement

二元整系数多项式

gPolyElement

二元整系数多项式

返回:

hPolyElement

多项式 \(f\) 和 \(g\) 的最大公约数

cffPolyElement

\(f\) 的辅因子，即 \(\frac{f}{h}\)

cfgPolyElement

\(g\) 的辅因子，即 \(\frac{g}{h}\)

参考文献

1. [Monagan00]

示例

>>> from sympy.polys.modulargcd import modgcd_bivariate
>>> from sympy.polys import ring, ZZ

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

sympy.polys.modulargcd.modgcd_multivariate(f, g)

使用模算法计算 \(\mathbb{Z}[x_0, \ldots, x_{k-1}]\) 中两个多项式的最大公约数。

该算法通过计算适合的素数 \(p\) 在 \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\) 中的 GCD，然后使用中国剩余定理重构系数，来计算两个多元整系数多项式 \(f\) 和 \(g\) 的 GCD。为了在 \(\mathbb{Z}_p\) 上计算多元 GCD，使用了递归子程序 _modgcd_multivariate_p()。为了在 \(\mathbb{Z}[x_0, \ldots, x_{k-1}]\) 中验证结果，进行了试除法，但仅针对非常可能是所需 GCD 的候选者。

参数:

fPolyElement

多元整系数多项式

gPolyElement

多元整系数多项式

返回:

hPolyElement

多项式 \(f\) 和 \(g\) 的最大公约数

cffPolyElement

\(f\) 的辅因子，即 \(\frac{f}{h}\)

cfgPolyElement

\(g\) 的辅因子，即 \(\frac{g}{h}\)

参见

_modgcd_multivariate_p

参考文献

1. [Monagan00]

2. [Brown71]

示例

>>> from sympy.polys.modulargcd import modgcd_multivariate
>>> from sympy.polys import ring, ZZ

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

sympy.polys.modulargcd._modgcd_multivariate_p(

f,

g,

p,

degbound,

contbound,

)

计算 \(\mathbb{Z}_p[x_0, \ldots, x_{k-1}]\) 中两个多项式的最大公约数。

该算法通过在合适的 \(a \in \mathbb{Z}_p\) 处对多项式 \(f\) 和 \(g\) 进行评估，逐步减少问题，即在 \(x_{k-1} = a\) 处进行评估，然后递归地调用自身以在 \(\mathbb{Z}_p[x_0, \ldots, x_{k-2}]\) 中计算GCD。如果这些递归调用对于足够多的评估点成功，则插值出 \(k\) 个变量的GCD，否则算法返回 None。每次计算GCD或内容时，它们的次数都会与边界进行比较。如果遇到大于边界的次数，则当前调用返回 None，并需要选择新的评估点。如果在某一点次数较小，则更新相应的边界，算法失败。

参数:

fPolyElement

系数在 \(\mathbb{Z}_p\) 中的多元整系数多项式

gPolyElement

系数在 \(\mathbb{Z}_p\) 中的多元整系数多项式

p整数

素数, \(f\) 和 \(g\) 的模数

degbound整数对象列表

degbound[i] 是 \(f\) 和 \(g\) 在变量 \(x_i\) 中的 GCD 的次数的上界。

contbound整数对象列表

contbound[i] 是 \(\mathbb{Z}_p[x_i][x_0, \ldots, x_{i-1}]\) 中GCD内容度的上界，contbound[0] 未被使用，因此可以任意选择。

返回:

hPolyElement

多项式 \(f\) 和 \(g\) 的最大公约数，或 None

参考文献

1. [Monagan00]

2. [Brown71]

sympy.polys.modulargcd.func_field_modgcd(f, g)

使用模算法计算多项式 \(f\) 和 \(g\) 在 \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\) 中的最大公约数。

该算法首先计算最小多项式 \(m_{\alpha}\) 在 \(\mathbb{Z}[z]\) 中的本原伴随 \(\check m_{\alpha}(z)\)，以及 \(f\) 和 \(g\) 在 \(\mathbb{Z}[x_1, \ldots, x_{n-1}][z]/(\check m_{\alpha})[x_0]\) 中的本原伴随。然后，它在 \(\mathbb Q(x_1, \ldots, x_{n-1})[z]/(m_{\alpha}(z))[x_0]\) 中计算 GCD。这是通过在合适的素数 \(p\) 下，在 \(\mathbb{Z}_p(x_1, \ldots, x_{n-1})[z]/(\check m_{\alpha}(z))[x_0]\) 中计算 GCD，然后使用中国剩余定理和有理重构来重构系数来完成的。在 \(\mathbb{Z}_p(x_1, \ldots, x_{n-1})[z]/(\check m_{\alpha}(z))[x_0]\) 上的 GCD 是通过递归子程序计算的，该子程序在 \(x_{n-1} = a\) 处对多项式进行评估，其中 \(a \in \mathbb Z_p\) 是合适的评估点，然后递归调用自身，直到基础域不再包含任何参数。对于 \(\mathbb{Z}_p[z]/(\check m_{\alpha}(z))[x_0]\)，使用欧几里得算法。这些递归调用的结果随后进行插值，并使用有理函数重构来获得正确的系数。结果，无论是在 \(\mathbb Q(x_1, \ldots, x_{n-1})[z]/(m_{\alpha}(z))[x_0]\) 还是在 \(\mathbb{Z}_p(x_1, \ldots, x_{n-1})[z]/(\check m_{\alpha}(z))[x_0]\) 中，都通过无分数试除法进行验证。

除了上述的GCD计算，在 \(\mathbb Q(\alpha)[x_1, \ldots, x_{n-1}]\) 中还需要计算一些GCD，因为将多项式视为单变量多项式可能会导致GCD的虚假内容。为此，func_field_modgcd 会被递归调用。

参数:

f, gPolyElement

多项式在 \(\mathbb Q(\alpha)[x_0, \ldots, x_{n-1}]\)

返回:

hPolyElement

多项式 \(f\) 和 \(g\) 的最大公约数

cffPolyElement

\(f\) 的余因子，即 \(\frac f h\)

cfgPolyElement

\(g\) 的辅因子，即 \(\frac g h\)

参考文献

1. [Hoeij04]

示例

>>> from sympy.polys.modulargcd import func_field_modgcd
>>> from sympy.polys import AlgebraicField, QQ, ring
>>> from sympy 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

未记录

polys 模块的许多部分仍然没有文档，即使有文档的地方，内容也很少。请贡献您的力量！