我正在寻找一种快速算法来在素数有限域中找到单变量多项式的根。
也就是说，如果(n > 0) ，那么对于给定的素数 p ，找到所有满足的算法。f = a0 + a1x + a2x2 + ... + anxnr < pf(r) = 0 mod p
我找到了 Chiens 搜索算法https://en.wikipedia.org/wiki/Chien_search但我无法想象这对于大于 20 位的素数来说会那么快。有没有人对 Chien 的搜索算法有经验或知道更快的方法？有没有一个 sympy 模块呢？
正如 mcdowella 的评论所表明的那样，这已经得到了很好的研究。以下是Cantor-Zassenhaus 随机算法在您想要找到多项式根的情况下的工作原理，而不是更一般的因式分解。
请注意，在系数 mod p 的多项式环中，乘积 x(x-1)(x-2)...(x-p+1) 具有所有可能的根，并且根据费马小定理等于 x^px和这个环中的独特因式分解。
设置 g = GCD(f,x^px)。使用Euclid 算法来计算两个多项式的 GCD 通常很快，它采用的步骤数在最大程度上是对数的。它不需要您对多项式进行因式分解。g在域中与f同根，无重复因子。
由于 x^px 的特殊形式，只有两个非零项，欧几里得算法的第一步可以通过重复平方来完成，大约 2 log_2 (p) 步，只涉及次数不超过 f 的两倍的多项式, 系数 mod p。我们可以计算 x mod f、x^2 mod f、x^4 mod f 等，然后将对应于 p 的二进制展开中非零位置的项相乘以计算 x^p mod f，最后减去 x。
重复执行以下操作： 在 Z/p 中选择一个随机 d。用 r_d = (x+d)^((p-1)/2)-1 计算 g 的 GCD，我们可以再次通过欧几里得算法快速计算，在第一步使用重复平方。如果这个 GCD 的次数严格在 0 和 g 的次数之间，我们找到了 g 的一个非平凡因子，我们可以递归直到我们找到线性因子，因此找到 g 的根，从而找到 f。
这多久工作一次？r_d 将 d 小于非零平方 mod p 的数字作为根。考虑 g 的两个不同根，a 和 b，因此 (xa) 和 (xb) 是 g 的因数。如果 a+d 是非零平方，而 b+d 不是，则 (xa) 是 g 和 r_d 的公因数，而 (xb) 不是，这意味着 GCD(g,r_d) 是 g 的非平凡因数. 类似地，如果 b+d 是非零平方而 a+d 不是，则 (xb) 是 g 和 r_d 的公因数，而 (xa) 不是。根据数论，一种情况或另一种情况接近 d 的可能选择的一半，这意味着平均而言，在我们找到 g 的非平凡因素之前，它需要恒定数量的 d 选择，实际上是一个分离 (xa)来自 (xb)。
你的答案很好，但我想我找到了一个很好的方法来找到以任何数字为模的根：这种方法基于“LATTICES”。令r ≤ R是mod p的根。我们必须找到另一个函数，例如h(x)使得h不大并且r是h的根。格法找到这个函数。首先，我们必须创建一个格的多项式基，然后，使用“LLL”算法，我们找到一个“最短向量”，其根为r而没有模p。事实上，我们用这种方式消除了模p 。
有关更多说明，请参阅“Coppersmith D. Find small solutions to small degree polynomials. In Cryptography and lattices”。