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

Therefore,

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.

### Like this:

Like Loading...

*Related*