Solving Systems of Polynomial Congruences Modulo a Large Prime * (Extended Abstract)
Ming-Deh A. Huang, Yiu-Chung Wong · Foundations of Computer Science · 1996
We consider the following polynomial congruences problem: given a prime p, and a set of polynomials fi , . . . , fm E Pp [X 1 , . . . , xn] of total degree at most d, solve the system f1 = . . . = fm = 0 for solution(s) in q, We give a randomized algorithm for the decision version of this problem. When the system has Fp -rational solutions our algorithm finds one of them as well as an approximation of the total number of such solutions. For afixed 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.