Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}^n 2^k y_k$, where $n = \lfloor \log_2 N \rfloor $ is one less the number of bits required to represent $N$, and $x_k, y_k$ are binary indeterminants. By abuse of notation, we can write the following system of equations (here $x, y \in \mathbb{C}^n$)
$\left\{ \begin{array}{lll} f_k= &x_k^2-x_k & =0 \\ g_k= &y_k^2-y_k &=0 \\ h= &\left( 1+ \sum_{k=1}^n 2^k x_k \right) \left( 1+ \sum_{k=1}^n 2^k y_k \right) -N & = 0 \end{array} \right.$
Finding the solution of this system using Groebner basis is computationally expensive (using standard algorithms). On the other hand, this system has only two solutions for semiprimes - $x$ encoding $p$, $y$ encoding $q$, and vice verse. Therefore, the Groebner basis will consist of $n-1$ linear equations encoding line passing through $p$ and $q$, and one quadratic equation selecting $p$ and $q$ along this line (in constrast to NP-complete problems, where many quadratic equations possible for the same problem with different input).
Q1. Does the knowledge of the form of Groebner basis helps to compute it?
Using ideas from Nullstellensatz linear algebra algorithm we can try to express Goebner basis using a linear combination of our equations with polynomial coefficients. For example linear part should be expressed as $c+ \sum_k a_k x_k +b_k y_k = P_1 h+ \sum_k P_{2,k} f_k + P_{3,k} g_k $ with $P_{...} \in \mathbb{C}[x_1,..., x_n, y_1, ..., y_n] $, Here the coefficients are treated as indeterminates. The nullspace of the solution in terms of coefficients of polynomials $P$ will lead to the solution of system of equations. My little experiments show that terms with monomial $x_1 ... x_n y_1...y_n$ are required on the right part of expression to obtain the solution (which is consistent with the Nullstellensatz certificate degree for the same system if it has no solution see DeLoera et al. paper Corollary 2.5).
In solving for $P$ we can start with all possible polynomials $P$ that lead to the monomial $x_1...x_n y_1...y_n$ with coefficients being indeterminates and find linear subspace of coefficients that eliminate it. Then, repeat this with (fixing monomial ordering) leading term in resulted polynomial on the right side. The naive application of this algorithm will lead to exponentially many monomials, on the other hand, the number of terms in encoding the solution line is at most quadratic with n.
Q2. Are there are any references that deal with optimization of monomial elimination in computing Nullstellensatz certificate?
Nullstellensatz certificate for the system of polynomials $f_k=0$ that does not have common solution in algebraically closed field $K$ is a set of polynomials $P_k \in K[...]$ that lead to expression $1= \sum_k P_k f_k $.
