Solving systems of polynomial congruences modulo a large prime
Solving systems of polynomial congruences modulo a large prime
复制标题
求解模大素数的多项式同余系统
DOI：
10.1109/sfcs.1996.548470
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Y. Wong
中科院分区：
文献类型：
--
作者：
Ming;Y. Wong
我们考虑以下多项式一致性问题：给定prime p，以及一组多项式f/sub 1/，...，f/sub m // spl isin/spl isin/f/sub p/[x/sub 1/。 。 /。我们为此问题提供了一种随机算法。当系统具有f/sub P/合理解时，我们的算法找到了其中一个以及此类溶液总数的近似值。对于固定数量的变量，该算法使用多项式的处理器数量，在D，M和P中，在D，M和P中具有并行复杂性的poly-logarithmic运行。作为该算法的重要步骤，我们还制定了一种代数同义方法，用于提取代数集的所有维度的组件。该方法有效地平行。
We consider the following polynomial congruences problem: given a prime p, and a set of polynomials f/sub 1/,...,f/sub m//spl isin/F/sub p/[x/sub 1/,...,x/sub n/] of total degree at most d, solve the system f/sub 1/=...=f/sub m/=0 for solution(s) in F/sub p//sup n/. We give a randomized algorithm for the decision version of this problem. When the system has F/sub p/-rational solutions our algorithm finds one of them as well as an approximation of the total number of such solutions. For a fixed number of variables, the algorithm runs in random polynomial time with parallel complexity poly-logarithmic in d, m and p, using a polynomial number of processors. As an essential step of the algorithm, we also formulate an algebraic homotopy method for extracting components of all dimensions of an algebraic set. The method is efficiently parallelizable.