Solvability of systems of polynomial congruences modulo a large prime (Q1590076)

The polynomial congruences problem is described as follows: given a prime number \(p\), and a set of polynomials \(f_1 ,f_2 , \cdots , f_m \in {\mathbb F}_p [x_1 , x_2 , \cdots , x_n ]\) of total degree at most \(d\), solve the system of congruences \(f_1 \equiv f_2 \equiv \cdots \equiv f_m \equiv 0 \pmod{p}\). The decision version of the problem is to decide whether or not the set of \({\mathbb F}_p\)-rational points of an algebraic set over \({\mathbb F}_p\) is empty. The main result of the work is the following: Theorem: Let \(k\) be a field over which the polynomial factorization can be done in randomized polynomial time. There is an algorithm that achieves the following. Given a set of polynomials \(f_1 ,f_2 , \cdots , f_m \in {\mathbb F}_p [x_1 , x_2 , \cdots , x_n ]\), let \(d = \max (n, \max \{ \deg f_i : 1 \leq i \leq m \})\). Assume that the size of \(k\) is greater than \(d^{cn^2}\) for some computable constant \(c\). Then the algorithm will construct a birational hypersurface \(h_W\) for each irreducible component \(W\) of \(V_k (f_1 , \cdots , f_m)\) with sequential complexity of \(m^{O(1)} d^{O(n^2)}\) field operations and with parallel complexity of a number of field operations polynomial on \(n\), \(\log m\) and \(\log d\) using \(m^{O(1)} d^{O(n^2)}\) processors such that the total degree of \(h_W\) is upper bounded by \(d^{2(n-\dim h_W +1)}\) and those of the rational functions defining the inverse map from \(h_W\) to \(W\) are in the order of \(d^{O(n- \dim h_W)}\). The algebraic set decomposition problem is, for the polynomials defined above (for \(k\) a finite field), decompose the algebraic set defined by the polynomials into irreducible components over \(k\), representing each of them by a birational hypersurface over \(k\), together with an inverse rational map from the hypersurface to the component. A method for solving this problem is given and used to prove the above theorem.