多项式在质数模意义下的根

Question

我正在寻找一种快速算法，可以在有限素域内查找一元多项式的根。

也就是说，如果 f = a0 + a1x + a2x2 + ... + anxn (n > 0)，那么对于给定的质数p，需要找到所有满足 f(r) = 0 mod p 的 r < p。

我发现了Chien搜索算法https://en.wikipedia.org/wiki/Chien_search，但我无法想象它在大于20位的质数上执行速度会很快。是否有人有关于Chien搜索算法的经验或知道更快的方法？是否有适用于此的sympy模块？

- Kevin Johnson

---

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.1907&rep=rep1&type=pdf 提出解决有限域上多项式问题是其分解的特例，并且存在随机多项式时间算法用于有限域上多项式的分解（参见例如http://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields）。它称将介绍确定性多项式时间算法用于根查找，但我尚未阅读到这一部分。 - mcdowella

Answer 1

这是一个被广泛研究的问题，正如mcdowella的评论所指出的那样。以下是 Cantor-Zassenhaus随机算法用于查找多项式根的情况，而不是更一般的分解的工作原理。

请注意，在模p系数的多项式环中，乘积x(x-1)(x-2)...(x-p+1)具有所有可能的根，并且等于x^p-x，根据费马小定理和此环中的唯一分解。

设置g = GCD(f, x^p-x)。使用欧几里得算法计算两个多项式的最大公因数通常很快，需要的步骤数取决于最高次数的对数。它不需要您将多项式因子化。g在域中具有与f相同的根，而且没有重复的因子。

由于x^p-x的特殊形式只有两个非零项，欧几里得算法的第一步可以通过重复平方完成，在p的二进制展开中涉及到的多项式次数不超过f的两倍，模p系数。我们可以计算x mod f、x^2 mod f、x^4 mod f等，然后将与p的二进制展开中的非零位对应的项相乘以计算x^p mod f，最后减去x。

重复执行以下操作：选择一个在Z/p中的随机数d。计算g与r_d = (x+d)^((p-1)/2)-1的GCD，我们可以使用欧几里得算法快速地进行计算，第一步使用重复平方。如果此GCD的次数严格介于0和g的次数之间，则我们已经找到了g的非平凡因子，并且我们可以递归直到找到线性因子，从而找到g和f的根。

这种方法的成功率有多高？r_d具有的根是模p时不为零的平方数减去d的数字。考虑g的两个不同根a和b，因此(x-a)和(x-b)是g的因子。如果a + d是非零平方数，而b+d不是，则(x-a)是g和r_d的公共因子，而(x-b)不是，这意味着GCD（g，r_d）是g的非平凡因子。同样地，如果b+d是非零平方数，而a+d不是，则(x-b)是g和r_d的公共因子，而(x-a)不是。根据数论，其中一种情况会发生近一半的可能性，这意味着平均只需进行常数次数的d选择，就可以找到g的非平凡因子，实际上是分离(x-a)和(x-b)。

- Douglas Zare

---

多项式GCD并不像我所说的那么快。步骤数受较小多项式的次数限制，在这里已经足够好了。 - Douglas Zare

Answer 2

您的答案很好，但我认为我找到了一种在任何数字模下找到根的奇妙方法：这个方法基于“格”。让r ≤ R是mod p的一个根。我们必须找到另一个函数h(x)，使得h不大且r是h的根。格方法可以找到这个函数。首先，我们必须为格子创建一个多项式基础，然后使用“LLL”算法找到一个“最短向量”，该向量具有没有模p的根r。实际上，我们通过这种方式消除了模p。

要了解更多信息，请参阅“Coppersmith D. Finding small solutions to small degree polynomials. In Cryptography and lattices”。

- Ruhollah. Js