On the bit complexity of polynomial system solving (Q1734694): Difference between revisions

Let \(R=\mathbb{Z}[X_1, \ldots , X_n]\) be the ring of polynomials in terms of the variables \(X_1, \ldots , X_n\) over \(\mathbb{Z}\). Let \(F_1, \ldots , F_r , G \in R\) be a sequence of polynomials such that the sequence \(F_1, \ldots , F_r\) forms a reduced regular sequence outside the variety \(V(G)\subset \mathbb{C}^n\). Thus, for any \(s\), the ideal \(I_s=\langle F_1, \ldots , F_s \rangle:G^\infty \subset \mathbb{Q}[X_1,\ldots ,X_n]\) is radical and equidimensional of dimension \(n-s\). In [ibid. 17, No. 1, 154--211 (2001; Zbl 1003.12005)], \textit{M. Giusti} et al. presented an algorithm to compute, in \(r\) stages, a suitable parametrization, so-called Kronecker representation for \(I_r\). In addition, in order to control the bit length of intermediate results, they proposed a method to perform the computations modulo a prime number. However, in this direction, the determination of a lucky prime is crucial. By studying this concept and applying \(p\)-adic lifting, the authors describe and analyze a randomized algorithm for solving a polynomial system (via computing its Kronecker representation) and show that its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size.