我正在寻找一种快速算法，以在质数有限域中找到单变量多项式的根。
也就是说，如果f = a + ax + ax + ... + ax(n> 0)，那么对于给定的素数p，找到满足r < p的所有f(r) = 0 mod p的算法。
我找到了Chiens搜索算法https://en.wikipedia.org/wiki/Chien_search，但是我无法想象对于大于20位的素数来说，速度是如此之快。是否有人对Chien的搜索算法有经验或知道更快的方法？为此有一个sympy模块吗？
最佳答案
正如mcdowella的评论所指出的，这已经被很好地研究了。这是Cantor-Zassenhaus random algorithm在您要查找多项式的根而不是更一般的因式分解的情况下的工作方式。
请注意，在系数为mod p的多项式环中，乘积x(x-1)(x-2)...(x-p + 1)具有所有可能的根，并且通过Fermat's Little Theorem和唯一因式分解等于x ^ px在这枚戒指中。
设置g = GCD(f，x ^ p-x)。通常，使用Euclid's algorithm计算两个多项式的GCD很快，最大程度地采取了许多对数的步骤。它不需要分解多项式。 g在该字段中具有与f相同的根，并且没有重复的因子。
由于x ^ px的特殊形式，只有两个非零项，因此Euclid算法的第一步可以由repeated squaring完成，大约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，我们可以再次使用Euclid算法快速计算，并在第一步中使用重复平方。如果此GCD的度严格在0和g的度之间，则我们发现g的非平凡因数，我们可以递归直到找到线性因数(因此g的根)和f的根。
这项工作多久进行一次？ r_d的根数小于非零平方模p的d。考虑g的两个不同的根a和b，因此(x-a)和(x-b)是g的因数。如果a + d是一个非零平方，而b + d不是，那么(xa)是g和r_d的公因数，而(xb)不是g的公因数，这意味着GCD(g，r_d)是g的非平凡因数。 。类似地，如果b + d是非零平方而a + d不是，那么(x-b)是g和r_d的公因数，而(x-a)不是。根据数论，一种情况或另一种情况几乎发生于d的可能选择的一半，这意味着在找到g的非平凡因子之前，平均而言，d的选择数是恒定的，实际上是一个分离(xa)来自(xb)。
关于algorithm - 多项式模的根为素数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29001275/