Kev*_*son 10 algorithm sympy polynomial-math polynomials
我正在寻找一种快速算法来找到素数有限域中单变量多项式的根.
也就是说,如果 (n> 0)那么对于给定的素数p ,找到满足的算法.f = a0 + a1x + a2x2 + ... + anxnr < pf(r) = 0 mod p
我发现了Chiens搜索算法https://en.wikipedia.org/wiki/Chien_search但是我无法想象这对于大于20位的素数来说是快速的.有没有人有使用Chien的搜索算法的经验或知道更快的方法？这是否有一个sympy模块？
Dou*_*are 13
正如mcdowella的评论所表明的那样,这是非常好的研究.以下是Cantor-Zassenhaus随机算法如何适用于您想要找到多项式的根的情况,而不是更通用的因子分解.
注意,在具有系数mod p的多项式环中,乘积x(x-1)(x-2)...(x-p + 1)具有所有可能的根,并且等于x ^ px由Fermat的Little Theorem和这个环中的独特因子分解.
设置g = GCD(f,x ^ px).使用欧几里德算法来计算两个多项式的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,我们可以通过Euclid算法再次使用第一步的重复平方快速计算.如果这个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).