Suppose we have , with and are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, , , where is one less the number of bits required to represent , and are binary indeterminates. By abuse of notation, we can write the following system of equations (here )
This system has only two solutions for semiprimes – encoding , encoding , and vice versa. Therefore, the Groebner basis will consist of linear equations encoding line passing through and , and one quadratic equation selecting these two points along this line.
Therefore, we want to represent the linear part of Groebner basis using a linear combination of our equations with polynomial coefficients – with , Here, the coefficients in the polynomials are treated as indeterminates. For example, for the correspondin system reads
The linear bases is expressed by
and we have the following system for coefficients of different monomials
So the left-hand side of the equation can be written as
What we can see here is that the matrix in the above expression has rank 2, unless , where the rank of the matrix is 1. When the nullspace of the matrix is
which correspond to two solutions – , and . Otherwise the null space is expressed as
So, for , and for .
Overall, despite we started with 9+3 indeterminates there are only 2 are relevant to the problem. The question is now how does it scales with . Or another question, is it at all possible to find an algorithm that will select only relevant monomials in .
Let’s try to extend analysis to the case .
To be continued.