Sign up ×  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 equa