多项式的根 mod 素数
Roots of a polynomial mod a prime
我正在寻找一种快速算法来求素数有限域中单变量多项式的根。
即如果f = a<sub>0</sub> + a<sub>1</sub>x + a<sub>2 </sub>x<sup>2</sup> + ... + a<sub>n</sub>x<sup>n</sup> (n > 0) 然后是一种算法，它找到所有 r < p 满足 f(r) = 0 mod p，对于给定的素数 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) 具有所有可能的根，并且等于 x^p-x Fermat's Little Theorem 和这个环中的唯一因式分解。
设 g = GCD(f,x^p-x)。使用 Euclid's algorithm 计算两个多项式的 GCD 通常很快，采取的步数在最大程度上是对数的。它不需要您分解多项式。 g在域上与f同根，无重复因子。
由于x^p-x的特殊形式，只有两个非零项，欧几里德算法的第一步可以用repeated squaring完成，大约2 log_2 (p)步涉及只有次数不超过 f 次数两倍的多项式，系数为 mod p。我们可以计算 x mod f、x^2 mod f、x^4 mod f 等，然后将对应于 p 的二进制展开中的非零位置的项相乘以计算x^pmodf，最后减去x。
重复执行以下操作：在Z/p中随机选择一个d。用 r_d = (x+d)^((p-1)/2)-1 计算 g 的 GCD，我们可以再次通过 Euclid 算法快速计算，在第一步中使用重复平方。如果这个 GCD 的次数严格在 0 和 g 的次数之间，我们就找到了 g 的一个非平凡因子，然后我们可以递归直到找到线性因子，即 g 的根和 f。
这项工作多久进行一次？ r_d 以比非零平方数 mod 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 的一个重要因素之前，它需要恒定数量的 d 选择，实际上是一个分离 (x-a)来自 (x-b).
你的答案很好，但我想我找到了一个很好的方法来求根 modulo 任意数：这个方法基于 "LATTICES"。设 r ≤ R 是 mod p。我们必须找到另一个函数，例如 h(x) 使得 h 不大并且 r是 h 的根。格子法求这个函数。首先，我们必须为格创建一个多项式的基础，然后用 "LLL" 算法，我们找到一个 "shortest vector" 有根 r 没有 modulo p。其实我们就是这样消去modulo p
更多解释请参考"Coppersmith D. Finding small solutions to small degree polynomials. In Cryptography and lattices"。
我正在寻找一种快速算法来求素数有限域中单变量多项式的根。
即如果f = a<sub>0</sub> + a<sub>1</sub>x + a<sub>2 </sub>x<sup>2</sup> + ... + a<sub>n</sub>x<sup>n</sup> (n > 0) 然后是一种算法，它找到所有 r < p 满足 f(r) = 0 mod p，对于给定的素数 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) 具有所有可能的根，并且等于 x^p-x Fermat's Little Theorem 和这个环中的唯一因式分解。
设 g = GCD(f,x^p-x)。使用 Euclid's algorithm 计算两个多项式的 GCD 通常很快，采取的步数在最大程度上是对数的。它不需要您分解多项式。 g在域上与f同根，无重复因子。
由于x^p-x的特殊形式，只有两个非零项，欧几里德算法的第一步可以用repeated squaring完成，大约2 log_2 (p)步涉及只有次数不超过 f 次数两倍的多项式，系数为 mod p。我们可以计算 x mod f、x^2 mod f、x^4 mod f 等，然后将对应于 p 的二进制展开中的非零位置的项相乘以计算x^pmodf，最后减去x。
重复执行以下操作：在Z/p中随机选择一个d。用 r_d = (x+d)^((p-1)/2)-1 计算 g 的 GCD，我们可以再次通过 Euclid 算法快速计算，在第一步中使用重复平方。如果这个 GCD 的次数严格在 0 和 g 的次数之间，我们就找到了 g 的一个非平凡因子，然后我们可以递归直到找到线性因子，即 g 的根和 f。
这项工作多久进行一次？ r_d 以比非零平方数 mod 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 的一个重要因素之前，它需要恒定数量的 d 选择，实际上是一个分离 (x-a)来自 (x-b).
你的答案很好，但我想我找到了一个很好的方法来求根 modulo 任意数：这个方法基于 "LATTICES"。设 r ≤ R 是 mod p。我们必须找到另一个函数，例如 h(x) 使得 h 不大并且 r是 h 的根。格子法求这个函数。首先，我们必须为格创建一个多项式的基础，然后用 "LLL" 算法，我们找到一个 "shortest vector" 有根 r 没有 modulo p。其实我们就是这样消去modulo p
更多解释请参考"Coppersmith D. Finding small solutions to small degree polynomials. In Cryptography and lattices"。