In integer factorization we are interested in finding the nontrivial divisor of the positive integer . Suppose we have factors and . We are interested in representing factors in binary form – , than we are interested in solving system of equations:

(1)

We assume . Each equation except the last one has exactly two solutions – . The last equation (given the constraint of the first equation) is encoding product of binary representation of integer numbers with K and M bits respectively. Therefore, the ideal of the system of polynomial equations (1) is either empty set, or the sets of points representing the possible factorization (and thus zero-dimensional). For example, it has two solution if both and are primes – and . We also can assume that both and are odd primes, than and .

Suppose, that we can determine the feasibility of the system (1) in a reasonable time. Then finding factors would be equal to testing recurrently whether the system is feasible with the K-th bit in x representation is equal to one or zero, and then testing next bit in feasible configuration, until all bits are determined. That would require testings.

Now we are interested in finding the fast algorithm for testing feasibility of system

(2)

Here, we will apply Nullstellensatz linear algebra (J.A. De Loera et al. / Journal of Symbolic Computation 46 (2011) 1260–1283) algorithm for testing the feasibility of the system of polynomial equations (2). The algorithm basically is based on Hilbert’s Nullstellensatz, in particular, a system of polynomial equations , where , and is algebraically closed field has no solution in if and only if there exist polynomials such that . Moreover, is called Nullstellensatz certificate. The idea behind Nullstellensatz linear algebra algorithm is to fix the degree of the polynomials to and write the polynomials in the general way – , where , , and the sum is taken over all monomials up to degree d. Then expanding the Nulsstellensatz certificate and equating coefficients in the left and right side one is looking to solve the system of linear equations on the coefficients.

For example, suppose K=M=1, then we have the following system

Now suppose we fix the degree of to 2, so the final polynomial is of order 4. In general , than Nullstellensatz certificate is

.

which defines 15 equations in 18 variables.

This system has infinitely many solutions unless n=1,3,9, which are the composite numbers represented by the 2-bit factors. The explicit certificate for equivalent system

is

.

We do not know the degree of the polynomials in advance. On the other hand, we can construct lower and upped bound. The upper bound can be computed using Corollary of Lazard lemma (p 1264 in De Loera paper)

**Corollary 2.5.** Given polynomials where is an algebraically closed field and d = max{ deg( ) }, if have no common zeros and have no common zeros at infinity, then where deg() ≤ n(d − 1).

The system (1) has no common zeros if infisible, and also has no common zeros at infinity, d=2, therefore deg, which lead to the linear system in coefficients.

On the other hand, the lower bound can be computed by equating the number of monomials in the certificate and the number of coefficients. Let (M+K)=m be the total number of variables. The number of coefficients is equal to the number of monomials times the number of equations in system (1), e.g. for degree d – , on the other hand the number of monomials in Nullstellensatz certificate correspond to the number of monomials for the polynomial with degree d+2, e.g . Than d should satisfy

. Therefore, the minimal number of monomials is , which is subexponential, and comparable to Quadratic sieve performance. To finish the work one needs to prove that the system of equations for coefficients is solvable.

Pingback: On the integer factorization and Nullstellensatz linear algebra: Fighting monomials. | Crackpot Trisector Notes