<p>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$)</p>

<p>$\left\{ \begin{array}{lll} f_k= &amp;x_k^2-x_k &amp; =0 \\ g_k= &amp;y_k^2-y_k &amp;=0  \\ h= &amp;\left( 1+ \sum_{k=1}^n 2^k x_k \right) \left( 1+ \sum_{k=1}^n 2^k y_k \right) -N &amp; = 0  \end{array} \right.$</p>

<p>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).</p>

<p><strong>Q1. Does the knowledge of the form of Groebner basis helps to compute it?</strong></p>

<p>Using ideas from <em>Nullstellensatz</em> linear algebra <a href="http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf">algorithm</a> 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 <em>Nullstellensatz</em> certificate degree for the same system if it has no solution see <a href="http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf">DeLoera et al.</a> paper Corollary 2.5). </p>

<p>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.</p>

<p><strong>Q2. Are there are any references that deal with optimization of monomial elimination in computing <em>Nullstellensatz</em> certificate?</strong></p>

<p><em>Nullstellensatz</em> 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 $.</p>

CC BY-SA 3.0
2012-10-25T13:03:19.050Z
You want to check the lower-bounds for Nullstellensatz proof system and lower-bound results on statements based on factoring in proof systems like Frege. (A proof system is like a non-deterministic algorithm, so a lower-bound for a proof system would rule out existence of deterministic algorithms based on that proof system.)
Kaveh
CC BY-SA 3.0
2012-10-26T05:04:09.033Z
@Kaveh Thanks, Kaveh. This is whole new world for me. Do you know good introductory texts on proof systems?
mkatkov
CC BY-SA 3.0
2012-10-26T05:12:23.237Z
I think [Nathan Segerlind's survey](http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps) can be a good point to start. Also check the Wikipedia article on [proof systems](http://en.wikipedia.org/wiki/Propositional_proof_system).
Kaveh
<ds.algorithms><nt.number-theory><factoring>
Semiprime factorization, Groebner bases and a Nullstellensatz certificate
mkatkov
# Semiprime factorization, Groebner bases and a Nullstellensatz certificate

(Asked by: username_0 on 2012-10-24)

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](http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf) 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.](http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf) 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 $.

**Tags:** ds.algorithms, nt.number-theory, factoring
> **Comments:**
> **username_1**: You want to check the lower-bounds for Nullstellensatz proof system and lower-bound results on statements based on factoring in proof systems like Frege. (A proof system is like a non-deterministic algorithm, so a lower-bound for a proof system would rule out existence of deterministic algorithms based on that proof system.)  
> **username_0**: @Kaveh Thanks, Kaveh. This is whole new world for me. Do you know good introductory texts on proof systems?  
> **username_1**: I think [Nathan Segerlind's survey](http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps) can be a good point to start. Also check the Wikipedia article on [proof systems](http://en.wikipedia.org/wiki/Propositional_proof_system).  

---

## 0 answers

