# An Algebraic-Geometry Approach to Prime Factorization

Alberto Montina, Stefan Wolf  Facoltà di Informatica, Università della
Svizzera italiana, 6900 Lugano, Switzerland

###### Abstract

New algorithms for prime factorization that outperform the existing ones or
take advantage of particular properties of the prime factors can have a
practical impact on present implementations of cryptographic algorithms that
rely on the complexity of factorization. Currently used keys are chosen on the
basis of the present algorithmic knowledge and, thus, can potentially be
subject to future breaches. For this reason, it is worth to investigate new
approaches which have the potentiality of giving a computational advantage.
The problem has also relevance in quantum computation, as an efficient quantum
algorithm for prime factorization already exists. Thus, better classical
asymptotic complexity can provide a better understanding of the advantages
offered by quantum computers. In this paper, we reduce the factorization
problem to the search of points of parametrizable varieties, in particular
curves, over finite fields. The varieties are required to have an arbitrarily
large number of intersection points with some hypersurface over the base
field. For a subexponential or polynomial factoring complexity, the number of
parameters have to scale sublinearly in the space dimension $n$ and the
complexity of computing a point given the parameters has to be subexponential
or polynomial, respectively. We outline a procedure for building these
varieties, which is illustrated with two constructions. In one case, we show
that there are varieties whose points can be evaluated efficiently given a
number of parameters not greater than $n/2$. In the other case, the bound is
dropped to $n/3$. Incidentally, the first construction resembles a kind of
retro-causal model. Retro-causality is considered one possible explanation of
quantum weirdness.

##  I Introduction

Prime factorization is a problem in the complexity class NP of problems that
can be solved in polynomial time by a nondeterministic machine. Indeed, the
prime factors can be verified efficiently by multiplication. At present, it is
not known if the problem has polynomial computational complexity and, thus, is
in the complexity class P. Nonetheless, the most common cryptographic
algorithms rely on the assumption of hardness of factorization. Website
certificates and bitcoin wallets are examples of resources depending on that
assumption. Since no strict lower bound on the computational complexity is
actually known, many critical services are potentially subject to future
security breaches. Consequently, cryptographic keys have gradually increased
their length to adapt to new findings. For example, the general number-field
sieve nfsieve  can break keys that would have been considered secure against
previous factoring methods.

Prime factorization is also important for its relation with quantum computing,
since an efficient quantum algorithm for factorization is known. This
algorithm is considered a main argument supporting the supremacy of quantum
over classical computing. Thus, the search for faster classical algorithms is
relevant for better understanding the actual gap between classical and quantum
realm.

Many of the known factoring methods use the ring of integers modulo $c$ as a
common feature, where $c$ is the number to be factorized. Examples are
Pollard’s $\rho$ and $p-1$ algorithms pollard1 ; pollard2 , Williams’ $p+1$
algorithm williams , their generalization with cyclotomic polynomials bach ,
Lenstra elliptic curve factorization lenstra , and quadratic sieve qsieve .
These methods end up to generate a number, say $m$, having a factor of $c$.
Once $m$ is obtained, the common factor can be efficiently computed by the
Euclidean algorithm. Some of these methods use only operations defined in the
ring. Others, such as the elliptic-curve method, perform also division
operations by pretending that $c$ is prime. If this operation fails at some
point, the divisor is taken as outcome $m$. In other words, the purpose of
these methods is to compute a zero over the field of integers modulo some
prime factor of $c$ by possibly starting from some random initial state. Thus,
the general scheme is summarized by a map $X\mapsto m$ from a random state $X$
in some set $\Omega$ to an integer $m$ modulo $c$. Different states may be
tried until $m$ is equal to zero modulo some prime of $c$. The complexity of
the algorithm depends on the computational complexity of generating $X$ in
$\Omega$, the computational complexity of evaluating the map, and the average
number of trials required to find a zero.

In this paper, we employ this general scheme by focusing on a class $\Theta$
of maps defined as multivariate rational functions over prime fields
$\mathbb{Z}_{p}$ of order $p$ and, more generally, over a finite field
$\text{GF}(q)$ of order $q=p^{k}$ and degree $k$. The set $\Omega$ of inputs
is taken equal to the domain of definition of the maps. More precisely, the
maps are first defined over some algebraic number field $\mathbb{Q}(\alpha)$
of degree $k_{0}$, where $\alpha$ is an algebraic number, that is, solution of
some irreducible polynomial $P_{I}$ of degree $k_{0}$. Then, the maps are
reinterpreted over a finite field. Using the general scheme of the other
methods, the class $\Theta$ takes to a factoring algorithm with polynomial
complexity if

  1. (a)

the number of distinct zeros, say $N_{P}$, of the maps in $\Theta$ is
arbitrarily large over $\mathbb{Q}(\alpha)$;

  2. (b)

a large fraction of the zeros remain distinct when reinterpreted over a finite
field whose order is greater than about $N_{P}^{1/M}$;

  3. (c)

the product of the number of parameters by the field degree is upper-bounded
by a sublinear power function of $\log N_{P}$;

  4. (d)

the computational complexity of evaluating the map given any input is upper-
bounded by a polynomial function in $\log N_{P}$.

A subexponential factoring complexity is achieved with weaker scaling
conditions on the map complexity, as discussed later in Sec. II.2. Later, this
approach to factorization will be reduced to the search of rational points of
a variety having an arbitrarily large number of rational intersection points
with a hypersurface.

The scheme employing rational functions resembles some existing methods, such
as Pollard’s $p-1$ algorithm. The main difference is that these algorithms
generally rely on algebraic properties over finite fields, whereas the present
scheme relies on algebraic properties over the field $\mathbb{Q}(\alpha)$. For
example, Pollard’s method ends up to build a polynomial $x^{n}-1$ with $p-1$
roots over a finite $\mathbb{Z}_{p}$, where $p$ is some prime factor of $c$.
This feature of the polynomial comes from Fermat’s little theorem and is
satisfied if the integer $n$ has $p-1$ as factor. Thus, the existence of a
large number of zeros of $x^{n}-1$ strictly depends on the field. Indeed, the
polynomial does not have more than $2$ roots over the rationals. In our
scheme, the main task is to find rational functions having a sufficiently
large number of zeros over an algebraic number field. This feature is then
inherited by the functions over finite fields. Some specific properties of
finite fields can eventually be useful, such as the reducibility of $P_{I}$
over $\mathbb{Z}_{p}$. This will be mentioned later.

Let us illustrate the general idea with an example. Suppose that the input of
the factorization problem is $c=pp^{\prime}$, with $p$ and $p^{\prime}$ prime
numbers and $p<p^{\prime}$. Let the map be a univariate polynomial of the form

$P(x)=\prod_{i=1}^{N_{P}}(x-x_{i}),$ (1)

where $x_{i}$ are integer numbers somehow randomly distributed in an interval
between $1$ and $i_{max}\gg p^{\prime}$. More generally, $x_{i}$ can be
rational numbers $n_{i}/m_{i}$ with $n_{i}$ and/or $m_{i}$ in
$\\{1,\dots,i_{max}\\}$. When reinterpreted modulo $p$ or modulo $p^{\prime}$,
the numbers $x_{i}$ take random values over the finite fields. If $N_{P}<p$,
we expect that the polynomial has about $N_{P}$ distinct roots over the finite
fields. Thus, the probability that $P(x)\mod p=0$ or $P(x)\mod p^{\prime}=0$
is about $N_{P}/p$ or $N_{P}/p^{\prime}$, respectively, which are the ratio
between the number of zeros and the size of the input space $\Omega$ over the
finite fields. The probability that $P(x)\mod c$ contains a nontrivial factor
of $c$ is about
$\frac{N_{P}}{p}\left(1-\frac{N_{P}}{p^{\prime}}\right)+\frac{N_{P}}{p^{\prime}}\left(1-\frac{N_{P}}{p}\right)$.
Thus, if $N_{P}$ is of the order of $p$, we can get a nontrivial factor by the
Euclidean algorithm in few trials. More specifically, if $p\simeq p^{\prime}$
and $N_{P}\simeq\sqrt{c}/2$, then the probability of getting a nontrivial
factor is roughly $1/2$. It is clear that a computational complexity of the
map scaling subexponentially or polynomially in $\log N_{P}$ leads to a
subexponential or polynomial complexity of the factoring algorithm. Thus, the
central problem is to build a polynomial $P(x)$ or a rational function with
friendly computational properties with respect to the number of zeros. The
scheme can be generalized by taking multivariate maps with $M$ input
parameters. In this case, the number of zeros needs to be of the order of
$p^{M}$, which is the size of the input space over the field $\mathbb{Z}_{p}$.
As a further generalization, the rational field can be replaced by an
algebraic number field $\mathbb{Q}(\alpha)$ of degree $k_{0}$. A number in
this field is represented as a $k_{0}$-dimensional vector over the rationals.
Reinterpreting the components of the vector over a finite field
$\mathbb{Z}_{p}$, the size of the sampling space is $p^{k_{0}M}$, so that we
should have $N_{P}\sim p^{k_{0}M}$ in order to get nontrivial factors in few
trials. Actually, this is the worst-case scenario since the reinterpretation
of $\mathbb{Q}(\alpha)$ modulo $p$ can lead to a degree of the finite field
much smaller than $k_{0}$. For example, if $\alpha$ is the root $e^{2\pi i/n}$
of the polynomial $x^{n}-1$, the degree of the corresponding finite field with
characteristic $p$ collapses to $1$ if $n$ is a divisor of $p-1$.

On one hand, it is trivial to build polynomials with an arbitrarily large
number $N_{P}$ of roots over the rationals as long as the computational cost
grows linearly in $N_{P}$. On the other hand, it is also simple to build
polynomials with friendly computational complexity with respect to $\log
N_{P}$ if the roots are taken over algebraically closed fields. The simplest
example is the previously mentioned polynomial $P(x)=x^{n}-1$, which has $n$
distinct complex roots and a computational complexity scaling as $\log n$.
However, over the rationals, this polynomial has at most $2$ roots. We can
include other roots by extending the rational field to an algebraic number
field, but the extension would have a degree proportional to the number of
roots, so that the computational complexity of evaluating $P(x)$ would grow
polynomially in the number of roots over the extension.

###  I.1 Algebraic-geometry rephrasing of the problem

It is clear that an explicit definition of each root of polynomial (1) leads
to an amount of memory allocation growing exponentially in $\log c$, so that
the resulting factoring algorithm is exponential in time and space. Thus, the
roots has to be defined implicitly by some simple rules. Considering a purely
algebraic definition, we associates the roots to rational solutions of a set
of $n$ non-linear polynomial equations in $n$ variables ${\bf
x}=(x_{1},\dots,x_{n})$,

$P_{k}({\bf x})=0,\;\;\;\;k\in\\{0,\dots,n-1\\}.$ (2)

The solutions are intersection points of $n$ hypersurfaces. The roots of
$P(x)$ are defined as the values of some coordinate, say $x_{n}$, at the
intersection points. By eliminating the $n-1$ variables $x_{1},\dots,x_{n-1}$,
we end up with a polynomial $P(x_{n})$ with a number of roots generally
growing exponentially in $n$. This solves the problem of space complexity in
the definition of $P(x)$. There are two remaining problems. First, we have to
choose the polynomials $P_{0},\dots,P_{n-1}$ such that an exponentially large
fraction of the intersection points are rational. Second, the variable
elimination, given a value of $x_{n}$, has to be performed as efficiently as
possible over a finite field. If the elimination has polynomial complexity,
then factorization turns out to have polynomial complexity. Note that the
elimination of $n-1$ variables given $x_{n}$ is equivalent to a consistency
test of the $n$ polynomials. The first problem can be solved in a simple way
by defining the polynomials as elements of the ideal generated by products of
linear polynomials. Let us denote a linear polynomial with a symbol with a
hat. For example, the quadratic polynomials

$G_{i}=\hat{a}_{i}\hat{b}_{i},\;\;\;\;\ i\in\\{1,\dots,n\\}$ (3)

have generally $2^{n}$ rational common zeros, provided that the coefficients
of $\hat{a}_{i}$ and $\hat{b}_{i}$ are rational. Identifying the polynomials
$P_{0},\dots,P_{n-1}$ with elements of the ideal generated
$G_{1},\dots,G_{n}$, we have

$P_{k}=\sum_{i}c_{k,i}({\bf
x})\hat{a}_{i}\hat{b}_{i},\;\;\;i\in\\{0,\dots,n-1\\},$ (4)

whose set of common zeros contains the $2^{n}$ rational points of the
generators $G_{i}$. In particular, if the polynomials $c_{k,i}$ are set equal
to constants, then the system $P_{0}=\dots P_{n-1}=0$ is equivalent to the
system $G_{1}=\dots G_{n}=0$.

At this point, the variable elimination is the final problem. A working method
is to compute a Gröbner basis. For the purpose of factorizing $c=pp^{\prime}$,
the task is to evaluate a Gröbner basis to check if the $n$ polynomials given
$x_{n}$ are consistent modulo $c$. If they are consistent modulo some non-
trivial factor $p$ of $c$, we end up at some point with some integer equal to
zero modulo $p$. However, the complexity of this computation is doubly
exponential in the worst case. Thus, we have to search for a suitable set of
polynomials with a large set of rational zeros such that there is an efficient
algorithm for eliminating $n-1$ variables. The variable elimination is
efficient if $n-1$ out of the $n$ polynomial equations $P_{k}=0$ form a
suitable triangular system for some set of low-degree polynomials $c_{k,i}$.
Let us assume that the last $n-1$ polynomials have the triangular form

$\left.\begin{array}[]{r}P_{n-1}(x_{n-1},x_{n})\\\
P_{n-2}(x_{n-2},x_{n-1},x_{n})\\\ \dots\\\
P_{1}(x_{1},\dots,x_{n-2},x_{n-1},x_{n})\end{array}\right\\},$

such that the $k$-th polynomial is linear in $x_{k}$. Thus, the corresponding
polynomial equations can be sequentially solved in the first $n-1$ variables
through the system

$\begin{array}[]{l}x_{n-1}=\frac{{\cal N}_{n-1}(x_{n})}{{\cal
D}_{n-1}(x_{n})}\\\ x_{n-2}=\frac{{\cal N}_{n-2}(x_{n},x_{n-1})}{{\cal
D}_{n-2}(x_{n},x_{n-1})}\\\ \dots\\\ x_{1}=\frac{{\cal
N}_{1}(x_{n},x_{n-1},\dots,x_{2})}{{\cal
D}_{1}(x_{n},x_{n-1},\dots,x_{2})},\end{array}$ (5)

where ${\cal D}_{k}\equiv\partial P_{k}/\partial x_{k}$ and ${\cal
N}_{k}\equiv P_{k}|_{x_{k}=0}$. This system defines a parametrizable curve,
say $\cal V$, in the algebraic set defined by the polynomials
$P_{1},\dots,P_{n-1}$, the variable $x_{n}$ being the parameter. Let us remind
that a curve is parametrizable if and only if its geometric genus is equal to
zero. The overall set of variables can be efficiently computed over a finite
field, provided that the polynomial coefficients $c_{k,i}$ are not too
complex. Once determined the variables, the remaining polynomial $P_{0}$ turns
out to be equal to zero if ${\bf x}$ is an intersection point. Provided that
the rational intersection points have distinct values of $x_{n}$ (which is
essentially equivalent to state that the points are distinct and are in the
variety $\cal V$), then the procedure generates a value $P_{0}({\bf x})$ which
is zero modulo $p$ with high probability if $p$ is of the order of the number
of rational intersection points. For this inference, it is pivotal to assume
that a large fraction of rational points remain distinct when reinterpreted
over the finite field.

This algebraic-geometry rephrasing of the problem can be stated in a more
general form. Let $\cal V$ and $\cal H$ be some irreducible curve in an
$n$-dimensional space and a hypersurface, respectively. The curve $\cal V$ is
not necessarily parametrizable, thus its genus may take strictly positive
values. The points in $\cal H$ are the zero locus of some polynomial $P_{0}$.
Let $N_{P}$ be the number of distinct intersection points between $\cal V$ and
$\cal H$ over the rational field $\mathbb{Q}$. Over a finite field
$\text{GF}(q)$, Weil’s theorem states that the number of rational points, says
$N_{1}$, of a smooth curve is bounded by the inequalities

$-2g\sqrt{q}\leq N_{1}-(q+1)\leq 2g\sqrt{q},$ (6)

where $g$ is the geometric genus of the curve. Generalizing to singular curves
aubry , we have

$-2g\sqrt{q}-\delta\leq N_{1}-(q+1)\leq 2g\sqrt{q}+\delta,$ (7)

where $\delta$ is the number of singularities, properly counted. These
inequalities have the following geometric interpretation. For the sake of
simplicity, let us assume that the singularities are ordinary double points. A
singular curve, says $\cal S$, with genus $g$ is birationally equivalent to a
smooth curve, say $\cal R$, with same genus, for which Wiel’s theorem holds.
That is, the rational points of $\cal R$ are bijectively mapped to the non-
singular rational points of $\cal S$, apart from a possible finite set
$\Omega$ of $2m$ points mapping to $m$ singular points of $\cal S$. The
cardinality of $\Omega$ is at most $2\delta$ (attained when the $\delta$
singularities have tangent vectors over the finite field). We have two
extremal cases. In one case, $\\#\Omega=2\delta$, so that, $\cal S$ has
$\delta$ points less than $\cal R$ (two points in $\Omega$ are merged into a
singularity of $\cal S$). This gives the lower bound in (7). In the second
case, $\Omega$ is empty and the singular points of $\cal S$ are rational
points. Thus, $\cal S$ has $\delta$ rational points more. Given this
interpretation, Weil’s upper bound still holds for the number of non-singular
rational points, say $N_{1}^{\prime}$,

$N_{1}^{\prime}\leq(q+1)+2g\sqrt{q}.$ (8)

Thus, if the genus is much smaller than $\sqrt{q}$, $N_{1}^{\prime}$ is upper-
bounded by a number close to the order of the field.

Now, let us assume that most of the $N_{P}$ rational points in ${\cal
V}\cap{\cal H}$ over $\mathbb{Q}$ remain distinct when reinterpreted over
$\mathbb{Z}_{p}$, with $p\simeq aN_{P}$, where $a$ is a number slightly
greater than $1$, say $a=2$. We also assume that these points are not
singularities of $\cal V$. Weil’s inequality (8) implies that the curve does
not have more than about $p$ points over $\mathbb{Z}_{p}$. Since $p\gtrsim
N_{1}^{\prime}\gtrsim N_{P}\sim p/2$, we have that the number of non-singular
rational points of the curve is about the number of intersection points over
$\mathbb{Z}_{p}$. This implies that a large fraction of points $\bf x\in\cal
V$ over the finite field are also points of $\cal H$. We have the following.

######  Claim 1.

Let ${\cal V}$ and ${\cal H}$ be an algebraic curve with genus $g$ and a
hypersurface, respectively. The hypersurface is the zero locus of the
polynomial $P_{0}$. Their intersection has $N_{P}$ distinct points over the
rationals, which are not singularities of $\cal V$. Let us also assume that
$g\ll\sqrt{N_{P}}$ and that most of the $N_{P}$ rational points remain
distinct over $\mathbb{Z}_{p}$ with $p\gtrsim 2N_{P}$. If we pick up at random
a point in $\cal V$, then

$P_{0}({\bf x})=0\mod p$ (9)

with probability equal to about ratio $N_{P}/p$.

If there are pairs $({\cal V},{\cal H})$ for every $N_{P}$ that satisfy the
premises of this claim, then prime factorization is reduced to the search of
rational points of a curve. Actually, these pairs always exist, as shown later
in the section. Assuming that $c=pp^{\prime}$ with $p\sim p^{\prime}$, the
procedure for factorizing $c$ is as follows.

  1. (1)

Take a pair $({\cal V},{\cal H})$ with $N_{P}\sim c^{1/2}$ such that the
premises of Claim 1 hold.

  2. (2)

Search for a rational point ${\bf x}\in\cal V$ over $Z_{p}$.

  3. (3)

Compute $\text{GCD}[P_{0}({\bf x}),c]$, the greatest common divisor of
$P_{0}({\bf x})$ and $c$.

The last step gives $\text{GCD}[P({\bf x}),c]$ equal to $1$, $c$ or one of the
factors of $c$. The probability of getting a nontrivial factor can be made
close to $1/2$ with a suitable tuning of $N_{P}$ (as shown later in Sec. II).

Finding rational points of a general curve with genus greater than $2$ is an
exceptionally complex problem. For example, just to prove that the plane curve
$x^{h}+y^{h}=1$ with $h>2$ does not have zeros over the rationals took more
than three centuries since Fermat stated it. Curves with genus $1$ are
elliptic curves, which have an important role in prime factorization (See
Lenstra algorithm lenstra ). Here, we will focus on parametrizable curves,
which have genus $0$. In particular, we will consider parametrizations
generated by the sequential equations (5). It is interesting to note that it
is always possible to find a curve $\cal V$ with parametrization (5) and a
hypersurface $\cal H$ such that their intersection contains a given set of
rational points. In particular, there is a set of polynomials
$P_{0},\dots,P_{n-1}$ of the form (4), such that the zero locus of the last
$n-1$ polynomials contains a parametrizable curve with parametrization (5),
whose intersection with the hypersurface $P_{0}=0$ contains $2^{n}$ distinct
rational points. Let the intersection points be defined by the polynomials
(3). Provided that $x_{n}$ is a separating variable, the set of intersection
points admits the rational univariate representation rouillier

$\left\\{\begin{array}[]{l}x_{n-1}=\frac{\bar{\cal N}_{n-1}(x_{n})}{{\bar{\cal
D}}_{n-1}(x_{n})}\\\ x_{n-2}=\frac{{\bar{\cal N}}_{n-2}(x_{n})}{\bar{\cal
D}_{n-2}(x_{n})}\\\ \dots\\\ x_{1}=\frac{\bar{\cal N}_{1}(x_{n})}{\bar{\cal
D}_{1}(x_{n})}\\\ {\bar{\cal N}}_{0}(x_{n})=0\end{array}\right.$ (10)

The first $n-1$ equations are a particular form of equation (5) and define a
parametrizable curve with $x_{n}$ as parameter. The last equation can be
replaced by some linear combination of the polynomials $G_{i}$. It is also
interesting to note that the rational univariate representation is unique once
the separating variable is chosen. This means that the parametrizable curve is
uniquely determined by the set of intersection points and the variable that is
chosen as parameter.

It is clear that the curve and hypersurface obtained through this construction
with a general set of polynomials $G_{i}$ satisfy the premises of Claim 1.
Indeed, a large part of the common zeros of the polynomials $G_{i}$ are
generally distinct over a finite field $\mathbb{Z}_{p}$ with $p\simeq N_{P}$.
For example, the point $\hat{a}_{1}=\dots=\hat{a}_{n}=0$ is distinct from the
other points if and only if $\hat{b}_{i}\neq 0$ at that point for every
$i\in\\{1,\dots,n\\}$. Thus, the probability that a given point is not
distinct over $\mathbb{Z}_{p}$ is of the order of $p^{-1}\sim N_{P}^{-1}$,
hence a large part of the points are distinct over the finite field. There is
an apparent paradox. With a suitable choice of the linear functions
$\hat{a}_{i}$ and $\hat{b}_{i}$, the intersection points can be made distinct
over a field $\mathbb{Z}_{p}$ with $p\ll N_{P}$, which contradicts Weil’s
inequality (8). The contradiction is explained by the fact that the curve is
broken into the union of reducible curves over the finite field. In other
words, some denominator ${\cal D}_{k}$ turns out to be equal to zero modulo
$p$ at some intersection points. This may happen also with $p\sim N_{P}$,
which is not a concern. Indeed, possible zero denominators can be used to find
factors of $c$.

###  I.2 Contents

In Section II, we introduce the general scheme of the factoring algorithm
based on rational maps and discuss its computational complexity in terms of
the complexity of the maps, the number of parameters and the field degree. In
Section III, the factorization problem is reduced to the search of rational
points of parametrizable algebraic varieties $\cal V$ having an arbitrarily
large number $N_{P}$ of rational intersection points with a hypersurface $\cal
H$. Provided that the $N_{P}$ grows exponentially in the space dimension, the
factorization algorithm has polynomial complexity if the number of parameters
and the complexity of evaluating a point in $\cal V$ over a finite field grow
sublinearly and polynomially in the space dimension, respectively. Thus, the
varieties $\cal V$ and $\cal H$ have to satisfy two requirements. On one side,
their intersection has to contain a large set of rational points. On the other
side, $\cal V$ has to be parametrizable and its points have to be computed
efficiently given the values of the parameters. The first requirement is
fulfilled with a generalization of the construction given by Eq. (4). First,
we define an ideal $I$ generated by products of linear polynomials such that
the associated algebraic set contains $N_{P}$ rational points. The relevant
information on this ideal is encoded in a satisfiability formula (SAT) in
conjunctive normal form (CNF) and a linear matroid. Then, we define $\cal V$
and $\cal H$ as elements of the ideal. By construction, ${\cal V}\cap{\cal H}$
contains the $N_{P}$ rational points. The ideal $I$ and the polynomials
defining the varieties contain some coefficients. The second requirement is
tackled in Sec. IV. By imposing the parametrization of $\cal V$, we get a set
of polynomial equations for the coefficients. These equations always admit a
solution, provided that the only constraint on $\cal V$ and $\cal H$ is being
an element of $I$. The task is to find an ideal $I$ and a set of coefficients
such that the computation of points in $\cal V$ is as efficient as possible,
given a number of parameters scaling sublinearly in the space dimension.

In this general form, the problem of building the varieties $\cal V$ and $\cal
H$ is quite intricate. A good strategy is to start with simple ideals and
search for varieties in a subset of these ideals, so that the polynomial
constraints on the unknown coefficients can be handled with little efforts.
With these restrictions, it is not guaranteed that the required varieties
exist, but we can have hints on how to proceed. This strategy is employed in
Sec. V, where we consider an ideal generated by the polynomials (3). The
varieties are defined by linear combinations of these generators with constant
coefficients, that is, $\cal H$ and $\cal V$ are in the zero locus of $P_{0}$
and $P_{1},\dots,P_{n-1}$, respectively, defined by Eq. (4). The $2^{n}$
rational points associated with the ideal are taken distinct in $\mathbb{Q}$.
First, we prove that there is no solution with one parameter ($M=1$), for a
dimension greater than $4$. We give an explicit numerical example of a curve
and hypersurface in dimension $4$. The intersection has $16$ rational points.
We also give a solution with about $n/2$ parameters. Suggestively, this
solution resembles a kind of retro-causal model. Retro-causality is considered
one possible explanation of some strange aspects of quantum theory, such as
non-locality and wave-function collapse after a measurement. Finally, we close
the section by proving that there is a solution with $2\leq M\leq(n-1)/3$.
This is shown by explicitly building a variety $\cal V$ with $(n-1)/3$
parameters. Whether it is possible to drop the number of parameters below this
upper bound is left as an open problem. If $M$ grows sublinearly in $n$, then
there is automatically a factoring algorithm with polynomial complexity,
provided that the coefficients defining the polynomials $P_{k}$ are in
$\mathbb{Q}$ and can be computed efficiently over a finite field. The
conclusions and perspectives are drawn in Sec. VI.

##  II General scheme and complexity analysis

At a low level, the central object of the factoring algorithm under study is a
class $\Theta$ of maps ${\vec{\tau}}\mapsto{\cal R}(\vec{\tau})$ from a set
$\vec{\tau}\equiv(\tau_{1},\dots,\tau_{M})$ of $M$ parameters over the field
$\mathbb{Q}(\alpha)$ to a number in the same field, where $\cal R$ is a
rational function, that is, the algebraic fraction of two polynomials. Let us
write it as

${\cal R}(\vec{\tau})\equiv\frac{{\cal N}(\vec{\tau})}{{\cal D}(\vec{\tau})}.$

This function may be indirectly defined by applying consecutively simpler
rational functions, as done in Sec. III. Note that the computational
complexity of evaluating ${\cal R}(\vec{\tau})$ can be lower than the
complexity of evaluating the numerator ${\cal N}(\vec{\tau})$. For this reason
we consider more general rational functions rather than polynomials. Both $M$
and $\alpha$ are not necessarily fixed in the class $\Theta$. We denote by
$N_{P}$ the number of zeros of the polynomial $\cal N$ over
$\mathbb{Q}(\alpha)$. The number $N_{P}$ is supposed to be finite, we will
come back to this assumption later in Sec. II.3.1. For the sake of simplicity,
first we introduce the general scheme of the algorithm over the rational
field. Then, we outline its extension to algebraic number fields. We mainly
consider the case of semiprime input, that is, $c$ is taken equal to the
product of two prime numbers $p$ and $p^{\prime}$. This case is the most
relevant in cryptography. If the rational points are somehow randomly
distributed when reinterpreted over $\mathbb{Z}_{p}$, then the polynomial
${\cal N}$ has at least about $N_{P}$ distinct zeros over the finite field,
provided that $N_{P}$ is sufficiently smaller than the size $p^{M}$ of the
input space $\Omega$. We could have additional zeros in the finite field, but
we conservatively assume that $N_{P}$ is a good estimate for the total number.
For $N_{P}$ close to $p^{M}$, two different roots in the rational field may
collapse to the same number in the finite field. We will account for that
later in Sec. II.2. Given the class $\Theta$, the factorization procedure has
the same general scheme as other methods using finite fields. Again, the value
$m={\cal R}(\tau_{1},\tau_{2},\dots)$ is computed by pretending that $c$ is
prime and $\mathbb{Z}/c\mathbb{Z}$ is a field. If an algebraic division takes
to a contradiction during the computation of $\cal R$, the divisor is taken as
outcome $m$. For the sake of simplicity, we neglect the zeros of $\cal D$ and
consider only the zeros of $\cal N$. In Section III, we will see that this
simplification is irrelevant for a complexity analysis. It is clear that the
outcome $m$ is zero in $\mathbb{Z}/c\mathbb{Z}$ with high probability for some
divisor $p$ of $c$ if the number of zeros is about or greater than the number
of inputs $p^{M}$. Furthermore, if $p^{\prime}>p$ and $N_{P}$ is sufficiently
smaller than $(p^{\prime})^{M}$, then the outcome $m$ contains the nontrivial
factor $p$ of $c$ with high probability. This is guaranteed if $N_{P}$ is
taken equal to about $c^{M/2}$, which is almost optimal if $p\simeq
p^{\prime}$, as we will see later in Sec. II.2. Thus, we have the following.

######  Algorithm 1.

Factoring algorithm with input $c=pp^{\prime}$, $p$ and $p^{\prime}$ being
prime numbers.

Choose a map in $\Theta$ with $M$ input parameters and $N_{P}$ zeros over the
rationals such that $N_{P}\simeq c^{M/2}$ (see Sec. II.2 for an optimal choice
of $N_{P}$);

generate a set of $M$ random numbers $\tau_{1},\dots,\tau_{M}$ over
$\mathbb{Z}/c\mathbb{Z}$.

compute the value $m={\cal R}(\tau_{1},\dots,\tau_{M})$ over
$\mathbb{Z}/c\mathbb{Z}$ (by pretending that $c$ is prime).

compute the greatest common divisor between $m$ and $c$.

if a nontrivial factor of $c$ is not obtained, repeat from point (2).

The number $M$ of parameters may depend on the map picked up in $\Theta$. Let
$M_{min}(N_{P})$ be the minimum of $M$ in $\Theta$ for given $N_{P}$. The
setting at point (1) is possible only if $M_{min}$ grows less than linearly in
$\log N_{P}$, which is condition (c) enumerated in the introduction. A tighter
condition is necessary if the computational complexity of evaluating the map
scales subexponentially, but not polynomially. This will be discussed with
more details in Sec. II.2.

If $c$ has more than two prime factors, $N_{P}$ must be chosen about equal to
about $p^{M}$, where $p$ is an estimate of one prime factor. If there is no
knowledge about the factors, the algorithm can be executed by trying different
orders of magnitude of $N_{P}$ from $2$ to $c^{1/2}$. For example, we can
increase the guessed $N_{P}$ by a factor $2$, so that the overall number of
executions grows polynomially in $\log_{2}p$. However, better strategies are
available. A map with a too great $N_{P}$ ends up to produce zero modulo $p$
for every factor $p$ of $c$ and, thus, the algorithm always generates the
trivial factor $c$. Conversely, a too small $N_{P}$ gives a too small
probability of getting a factor. Thus, we can employ a kind of bisection
search. A sketch of the search algorithm is as follows.

  1. 1.

set $a_{d}=1$ and $a_{u}=c^{M}$;

  2. 2.

set $N_{P}=\sqrt{a_{d}a_{u}}$ and choose a map in $\Theta$ with $N_{P}$ zeros;

  3. 3.

execute Algorithm 1 from point (2) and break the loop after a certain number
of iterations;

  4. 4.

if a nontrivial factor is found, return it as outcome;

  5. 5.

if the algorithm found only the trivial divisor $c$, set $a_{u}=N_{P}$,
otherwise set $a_{d}=N_{P}$;

  6. 6.

go back to point (2).

This kind of search can reduce the number of executions of Algorithm 1. In the
following, we will not discuss these optimizations for multiple prime factors,
we will consider mainly semiprime integer numbers $c=pp^{\prime}$.

###  II.1 Extension to algebraic number fields

Before outlining how the algorithm can be extended to algebraic number fields,
let us briefly remind what a number field is. The number field
$\mathbb{Q}(\alpha)$ is a rational field extension obtained by adding an
algebraic number $\alpha$ to the field $\mathbb{Q}$. The number $\alpha$ is
solution of some irreducible polynomial $P_{I}$ of degree $k_{0}$, which is
also called the degree of $\mathbb{Q}(\alpha)$. The extension field includes
all the elements of the form $\sum_{i=0}^{k_{0}-1}r_{i}\alpha^{i}$, where
$r_{i}$ are rational numbers. Every power $\alpha^{h}$ with $h\geq k_{0}$ can
be reduced to that form through the equation $P_{I}(\alpha)=0$. Thus, an
element of $\mathbb{Q}(\alpha)$ can be represented as a $k_{0}$-dimensional
vector over $\mathbb{Q}$. Formally, the extension field is defined as the
quotient ring $\mathbb{Q}[X]/P_{I}$, the polynomial ring over $\mathbb{Q}$
modulo $P_{I}$. The quotient ring is also a field as long as $P_{I}$ is
irreducible. Reinterpreting the rational function $\cal R$ over a finite field
$\text{GF}(p^{k})$ means to reinterpret $r_{i}$ and the coefficients of
$P_{I}$ as integers modulo a prime number $p$. Since the polynomial $P_{I}$
may be reducible over $\mathbb{Z}_{p}$, the degree $k$ of the finite field is
some value between $1$ and $k_{0}$ and equal to the degree of one the
irreducible factors of $P_{I}$. Let $D_{1},\dots,D_{f}$ be the factors of
$P_{I}$. Each $D_{i}$ is associated with a finite field
$\mathbb{Z}_{p}[X]/D_{i}\cong\text{GF}(p^{k_{i}})$, where $k_{i}$ is the
degree of $D_{i}$. Smaller values of $k$ take to a computational advantage, as
the size $p^{kM}$ of the input space $\Omega$ is smaller and the probability,
about $N_{P}/p^{kM}$, of getting the factor $p$ is higher. For example, the
cyclotomic number field with $\alpha=e^{2\pi i/n}$ has a degree equal to
$\phi(n)$, where $\phi$ is the Euler totient function, which is asymptotically
lower-bounded by $Kn/\log\log n$, for every constant $K<e^{-\gamma}$, $\gamma$
being the Euler constant. In other words, the highest degree of the polynomial
prime factors of $x^{n}-1$ is equal to $\phi(n)$. Let $P_{I}$ be equal to the
factor with $e^{2\pi i/n}$ as root. If $n$ is a divisor of $p-1$ for some
prime number $p$, then $P_{I}$ turns out to have linear factors over
$\mathbb{Z}_{p}$. Thus, the degree of the number field collapses to $1$ when
mapped to a finite field with characteristic $p$. Thus, the bound $k_{0}$ sets
a worst case.

For general number fields, the equality $k=k_{0}$ is more an exception than a
rule, apart from the case of the rational field, for which $k=k_{0}=1$. For
the sake of simplicity, let us assume for the moment that $k=k_{0}$ for one of
the two factors of $c$, say $p^{\prime}$. Algorithm 1 is modified as follows.
The map is chosen at point (1) of Algorithm 1 such that $N_{P}\simeq
c^{k_{0}M/2}$; the value $m$ computed at point (3) is a polynomial over
$\mathbb{Z}/c\mathbb{Z}$ of degree $k_{0}-1$; the greatest common divisor at
point (4) is computed between one of the coefficients of the polynomial $m$
and $c$. If the degree $k$ of the finite field of characteristic $p$ turns out
to be smaller than $k_{0}$, we have to compute the polynomial greatest common
divisor between $m$ and $P_{I}$ by pretending again that
$\mathbb{Z}/c\mathbb{Z}$ is a field. If $m$ is zero over $\text{GF}(p^{k})$,
then the Euclidean algorithm generates at some point a residual polynomial
with the leading coefficient having $p$ as a factor (generally, all the
coefficients turn out to have $p$ as a factor). If $k\neq k_{0}$ for both
factors and most of the maps, then the algorithm ends up to generate the
trivial factor $c$, so that we need to decrease $N_{P}$ until a non-trivial
factor is found.

###  II.2 Complexity analysis

The computational cost of the algorithm grows linearly with the product
between the computational cost of the map, say ${\bf C}_{0}({\cal R})$, and
the average number of trials, which is roughly $p^{k_{0}M}/N_{P}$ provided
that $N_{P}\ll p^{k_{0}M}$ and $P_{I}$ is irreducible over $\mathbb{Z}_{p}$.
The class $\Theta$ may contain many maps with a given number $N_{P}$ of zeros
over some number field. We can choose the optimal map for each $N_{P}$, so
that we express $k_{0}$, $M$ and $\cal R$ as functions of $\log
N_{P}\equiv\xi$. The computational cost ${\bf C}_{0}({\cal R})$ is written as
a function of $\xi$, ${\bf C}_{0}(\xi)$.

Let us evaluate the computational complexity of the algorithm in terms of the
scaling properties of $k_{0}(\xi)$, $M(\xi)$ and ${\bf C}_{0}({\xi})$ as
functions of $\xi=\log N_{P}$. The complexity ${\bf C}_{0}(\xi)$ is expected
to be a monotonically increasing function. If the functions $k_{0}(\xi)$ and
$M(\xi)$ were decreasing, then they would asymptotically tend to a constant,
since they are not less than $1$. Thus, we assume that these two functions are
monotonically increasing or constant.

As previously said, the polynomial $\cal N$ has typically about $N_{P}$
distinct roots over $\text{GF}(p^{k_{0}})$, provided that $N_{P}$ is
sufficiently smaller than $p^{k_{0}M}$. If $N_{P}$ is greater than
$p^{k_{0}M}$, then almost every value of $\vec{\tau}$ is a zero of the
polynomial. Assuming that the zeros are somehow randomly distributed, the
probability that a number picked up at random is different from any zero over
$\text{GF}(p^{k_{0}})$ is equal to $(1-p^{-k_{0}M})^{N_{P}}$. Thus, the number
of roots over $\text{GF}(p^{k_{0}})$ is expected to be of the order of
$p^{k_{0}M}[1-(1-p^{-k_{0}M})^{N_{P}}]$, which is about $N_{P}$ for $N_{P}\ll
p^{k_{0}M}$. Thus, the average number of trials required for getting a zero is

$N_{trials}\equiv\frac{1}{1-(1-p^{-k_{0}M})^{N_{P}}},$ (11)

A trial is successful if it gives zero modulo some nontrivial factor of $c$,
thus the number of required trials can be greater than $N_{trials}$ if some
factors are close each other. Let us consider the worst case with
$c=pp^{\prime}$, where $p$ and $p^{\prime}$ are two primes with
$p^{\prime}\simeq p$ such that $(p^{\prime})^{k_{0}M}\simeq p^{k_{0}M}$.
Assuming again that the roots are randomly distributed, the probability of a
successful trial is $\text{Pr}_{\text{succ}}\equiv
2[1-(1-p^{-k_{0}M})^{N_{P}}](1-p^{-{k_{0}}M})^{N_{P}}$. The probability has a
maximum equal to $1/2$ for $\xi$ equal to the value

$\xi_{0}\equiv\log\left[-\frac{\log 2}{\log(1-p^{-k_{0}M})}\right].$ (12)

Evaluating the Taylor series at $p=\infty$, we have that

$\xi_{0}=k_{0}M\log p+\log\log 2-\frac{1}{2p^{k_{0}M}}+O(p^{-2k_{0}M}).$ (13)

The first two terms give a very good approximation of $\xi_{0}$. At the
maximum, the ratio between the number of zeros and the number of states
$p^{k_{0}M}$ of the sampling space is about $\log 2$. It is worth to note
that, for the same value of $\xi$, the probability of getting an isolated
factor with $p\ll p^{\prime}$ is again exactly $1/2$. Thus, we have in general

$N_{P}\simeq 0.69p^{k_{0}M}\Rightarrow\text{Pr}_{\text{succ}}=1/2.$ (14)

Since the maximal probability is independent of $k_{0}$ and $M$, this value is
also maximal if $k_{0}$ and $M$ are taken as functions of $\xi$. The maximal
value $\xi_{0}$ is solution of the equation

$\xi_{0}=\log\left[-\frac{\log 2}{\log(1-p^{-f(\xi_{0})})}\right].$ (15)

where $f(\xi)\equiv k_{0}(\xi)M(\xi)$. If the equation has no positive
solution, then the probability is maximal for $\xi=0$. That is, the optimal
map in the considered class is the one with $N_{P}=1$. This means that the
number of states $p^{k_{0}M}$ of the sampling space grows faster than the
number of zeros. In particular, there is no solution for $\log p$ sufficiently
large if $f(\xi)$ grows at least linearly (keep in mind that $f(\xi)\geq 1$).
Thus, the function $f(\xi)$ has to be a sublinear power function, as
previously said.

The computational cost of the algorithm for a given map ${\cal R}(\xi)$ is

${\bf C}(p,\xi)\equiv\frac{{\bf
C}_{0}(\xi)}{2[1-(1-p^{-f(\xi)})^{\exp\xi}](1-p^{-f(\xi)})^{\exp\xi}}.$ (16)

The optimal map for given $p$ is obtained by minimizing ${\bf C}(p,\xi)$ with
respect to $\xi$. The computational complexity of the algorithm is

${\bf C}(p)=\min_{\xi>0}{\bf C}(p,\xi)\equiv{\bf C}(p,\xi_{m}),$ (17)

which satisfies the bounds

${\bf C}_{0}(\xi_{m})\leq{\bf C}(p)\leq 2{\bf C}_{0}(\xi_{0}).$ (18)

The upper bound in Eq. (18) is the value of ${\bf C}(p,\xi)$ at $\xi=\xi_{0}$,
whereas the lower bound is the computational complexity of the map at the
minimum $\xi_{m}$.

It is intuitive that the complexity ${\bf C}_{0}(\xi)$ must be subexponential
in order to have ${\bf C}(p)$ subexponential in $\log p$. This can be shown by
contradiction. Suppose that the complexity ${\bf C}(p)$ is subexponential in
$\log p$ and ${\bf C}_{0}(\xi)=\exp(a\xi)$ for some positive $a$. The lower
bound in Eq. (18) implies that the optimal $\xi_{m}$ grows less than $\log p$.
Asymptotically,

$\left.\frac{p^{k_{0}M}}{N_{P}}\right|_{\xi=\xi_{m}}\sim e^{f(\xi_{m})\log
p-\xi_{m}}\geq Kp^{1/2},$ (19)

for some constant $K$. Thus, the average number of trials grows exponentially
in $\log p$, implying that the computational complexity is exponential, in
contradiction with the premise. Since $f(\xi)$ and $\log{\bf C}_{0}(\xi)$ must
grow less than linearly, we may assume that they are concave.

######  Property 1.

The functions $f(\xi)$ and $\log{\bf C}_{0}(\xi)$ are concave, that is,

$\frac{d^{2}}{d\xi^{2}}f(\xi)\leq 0,\;\;\;\frac{d^{2}}{d\xi^{2}}\log{\bf
C}_{0}(\xi)\leq 0.$ (20)

The lower bound in Eq. (18) depends on $\xi_{m}$, which depends on the
function $C_{0}(\xi)$. A tighter bound which is also simpler to evaluate can
be derived from Property 1 and the inequality

${\bf C}(p,\xi)\geq\frac{1}{2}e^{f(\xi)\log p-\xi}{\bf C}_{0}(\xi).$ (21)

######  Lemma 1.

If Property 1 holds and ${\bf C}(p)$ is asymptotically sublinear in $p$, then
there is an integer $\bar{p}$ such that the complexity ${\bf C}(p)$ is bounded
from below by $\frac{{\bf C}_{0}(\xi_{0})}{2\log 2}$ for $p>\bar{p}$.

Proof. The minimum $\xi_{m}$ is smaller than $\xi_{0}$, since the function
${\bf C}_{0}(\xi)$ is monotonically increasing. Thus, we have

${\bf C}(p)=\min_{\xi\in\\{0,\xi_{0}\\}}{\bf
C}(p,\xi)\geq\min_{\xi\in\\{0,\xi_{0}\\}}e^{f(\xi)\log p-\xi+\log
C_{0}(\xi)}/2.$ (22)

Since the exponential is monotonic and the exponent is concave, the objective
function has a maximum and two local minima at the $\xi=0$ and $\xi=\xi_{0}$.
Keeping in mind that $f(\xi)\geq 1$, The first local minimum is not less than
$p{\bf C}_{0}(0)/2$. The second minimum is $e^{f(\xi_{0})\log p-\xi_{0}}{\bf
C}_{0}(\xi_{0})/2$, which is greater than or equal to ${\bf
C}_{0}(\xi_{0})/(2\log 2)$. This can be proved by eliminating $p$ through Eq.
(15) and minimizing in $\xi_{0}$. Since ${\bf C}(p)$ is sublinear in $p$,
there is an integer $\bar{p}$ such that the second minimum is global for
$p>\bar{p}$. $\square$

Summarizing, we have

$0.72{\bf C}_{0}(\xi_{0})\leq{\bf C}(p)\leq 2{\bf C}_{0}(\xi_{0})$ (23)

for $p$ greater than some integer. Thus, the complexity analysis of the
algorithm is reduced to study the asymptotic behavior of ${\bf
C}_{0}(\xi_{0})$. The upper bound is asymptotically tight, that is,
$\xi=\xi_{0}$ is asymptotically optimal. Taking

$f(\xi)=b\xi^{\beta}\text{ with }\beta\in[0:1),$

the optimal value of $\xi$ is

$\xi_{0}=(b\log p)^{\frac{1}{1-\beta}}+O(1).$

The function $f(\xi)$ cannot be linear, but we can take it very close to a
linear function,

$f(\xi)=b\frac{\xi}{(\log\xi)^{\beta}},\;\;\;\;\gamma>1.$ (24)

In this case, the optimal $\xi$ is

$\xi_{0}=e^{(b\log p)^{1/\beta}}+O\left[(\log p)^{1/\beta}\right].$

There are three scenarios taking to subexponential or polynomial complexity.

  1. (a)

The functions ${\bf C}_{0}(\xi)$ and $f(\xi)$ scale polynomially as
$\xi^{\alpha}$ and $\xi^{\beta}$, respectively, with $\beta\in[0:1)$. Then,
the computational complexity ${\bf C}(p)$ scales polynomially in $\log p$ as
$(\log p)^{\frac{\alpha}{1-\beta}}$.

  2. (b)

The function ${\bf C}_{0}(\xi)$ is polynomial and
$f(\xi)\sim\xi/(\log\xi)^{\beta}$ with $\beta>1$. Then the computational
complexity ${\bf C}(p)$ scales subexponentially in $\log p$ as
$\exp\left[b(\log p)^{1/\beta}\right]$.

  3. (c)

The function ${\bf C}_{0}(\xi)$ and $f(\xi)$ are superpolynomial and
polynomial respectively, with ${\bf
C}_{0}(\xi)\sim\exp\left[b\xi^{\alpha}\right]$ and $f(\xi)\sim\xi^{\beta}$. If
$\alpha+\beta<1$, then the complexity ${\bf C}(p)$ is subexponential in $\log
p$ and scales as $\exp\left[b(\log p)^{\frac{\alpha}{1-\beta}}\right]$.

The algorithm has polynomial complexity in the first scenario. The other cases
are subexponential. This is also implied by the following.

######  Lemma 2.

The computational complexity ${\bf C}(p)$ is subexponential or polynomial in
$\log p$ if the function ${\bf C}_{0}(\xi)^{f(\xi)}$ grows less than
exponentially, that is, if

$\lim_{\xi\rightarrow\infty}\frac{f(\xi)\log{\bf C}_{0}(\xi)}{\xi}=0.$

In particular, the complexity is polynomial if ${\bf C}_{0}(\xi)$ is
polynomial and $f(\xi)$ scales sublinearly.

This lemma can be easily proved directly from Eq. (15) and the upper bound in
Eq. (18), the former implying the inequality $\xi_{0}\leq f(\xi_{0})\log
p+\log\log 2$. Let us prove the first statement.

$\lim_{p\rightarrow\infty}\frac{\log{\bf C}(p)}{\log
p}\leq\lim_{\xi\rightarrow\infty}\frac{f(\xi)\log 2{\bf
C}_{0}(\xi)}{\xi-\log\log 2}=\lim_{\xi\rightarrow\infty}\frac{f(\xi)\log{\bf
C}_{0}(\xi)}{\xi}=0.$

Using the lower bound in Eq. (23), the lemma can be strengthened by adding the
inferences in the other directions (_if_ replaced by _if and only if_).

Summarizing, we have the following.

######  Claim 2.

The factoring algorithm 1 has subexponential (_polynomial_) complexity if, for
every $\xi=\log N_{P}>0$ with $N_{P}$ positive integer, there are rational
univariate functions ${\cal R}(\vec{\tau})=\frac{{\cal N}(\vec{\tau})}{{\cal
D}(\vec{\tau})}$ of the parameters $\vec{\tau}=(\tau_{1},\dots,\tau_{M(\xi)})$
over an algebraic number field $\mathbb{Q}(\alpha)$ of degree $k_{0}(\xi)$
with polynomials $\cal N$ and $\cal D$ coprime, such that

  1. 1.

the number of distinct roots of $\cal N$ in $\mathbb{Q}(\alpha)$ is equal to
about $N_{P}$. Most of the roots remain distinct when interpreted over finite
fields of order equal to about $N_{P}^{1/M}$;

  2. 2.

given any value $\vec{\tau}$, the computation of ${\cal R}(\vec{\tau})$ takes
a number ${\bf C}_{0}(\xi)$ of arithmetic operations growing less than
exponentially (_polynomially_) in $\xi$;

  3. 3.

the function ${\bf C}_{0}(\xi)^{k_{0}(\xi)M(\xi)}$ is subexponential (_the
function $k_{0}(\xi)M(\xi)$ scales sublinearly_).

Let us stress that the asymptotic complexity is less than exponential if and
only if ${\bf C}_{0}(\xi)^{f(\xi)}$ is less than exponential. Thus, the latter
condition is a litmus test for a given class of rational functions. However,
the function ${\bf C}_{0}(\xi)^{f(\xi)}$ does not provide sufficient
information on the asymptotic computational complexity of the factoring
algorithm. The general number-field sieve is the algorithm with the best
asymptotic complexity, which scales as $e^{a(\log p)^{1/3}}$. Thus, algorithm
1 is asymptotically more efficient than the general number-field sieve if
${\bf C}_{0}(\xi)$ and $f(\xi)$ are asymptotically upper-bounded by a
subexponential function $e^{b(\log p)^{\alpha}}$ and a power function
$c\xi^{\beta}$, respectively, such that $\alpha<(1-\beta)/3$. In the limit
case of $\beta\rightarrow 1$ and polynomial complexity of the map, the
function $f(\xi)$ must be asymptotically upper-bounded by
$b\xi/(\log\xi)^{3}$.

###  II.3 Number of rational zeros versus polynomial degree

Previously we have set upper bounds on the required computational complexity
of the rational function $\cal R={\cal N}/{\cal D}$ in terms of the number of
its rational zeros. For a polynomial (subexponential) complexity of prime
factorization, the computational complexity ${\bf C}_{0}$ of $\cal R$ must
scale polynomially (subexponentially) in the logarithm in the number of
rational zeros. Thus, for a univariate rational function, it is clear that
${\bf C}_{0}$ has to scale polynomially (subexponentially) in the logarithm of
the degree $d$ of $\cal N$, since the number of rational zeros is upper-
bounded by the degree (fundamental theorem of algebra). An extension of this
inference to multivariate functions is more elaborate, as upper bounds on the
number of rational zeros are unknown. However, we are interested more properly
to a set of $N_{P}$ rational zeros that remain in great part distinct when
reinterpreted over a finite field whose order is greater than about
$N_{P}^{1/M}$. Under this restriction, let us show that the number of rational
zeros of a polynomial of degree $d$ and with $M$ variables is upper-bounded by
$Kd^{2M}$ with some constant $K>0$. This bound allows us to extend the
previous inference on ${\bf C}_{0}$ to the case of multivariate functions.

Assuming that the $N_{P}$ rational zeros over $\mathbb{Q}$ are randomly
distributed when reinterpreted over $\text{GF}(q)$, their number over the
finite field is about $q^{M}\left[1-(1-q^{-M})^{N_{P}}\right]$, as shown
previously. Since an upper bound on the number of zeros $N(q)$ of a smooth
hypersurface over a finite field of order $q$ is known, we can evaluate an
upper bound on $N_{P}$. Given the inequality katz

$N(q)\leq\frac{q^{M}-1}{q-1}+\left[(d-1)^{M}-(-1)^{M}\right]\left(1-d^{-1}\right)q^{(M-1)/2}$
(25)

and

$q^{M}\left[1-(1-q^{-M})^{N_{P}}\right]\leq N(q),$ (26)

we get an upper bound on $N_{P}$ for each $q$. Requiring that Eq. (26) is
satisfied for every $q>N_{P}^{1/M}$, we get

$N_{P}<Kd^{\frac{2M^{2}}{M+1}}<Kd^{2M}$ (27)

for some constant $K$ (the same result is obtained by assuming that Eq. (26)
holds for every $q$). Note that a slight break of bound (27) with $N_{P}$
growing as $d_{0}^{M^{a}}$ in $M$ for some particular $d=d_{0}$ and $a>1$
would make the complexity of prime factorization polynomial, provided the
computational complexity of evaluating the function ${\cal R}$ is polynomial
in $M$. This latter condition can be actually fulfilled, as shown with an
example later. Ineq. (25) holds for smooth irreducible hypersurfaces. However,
dropping these conditions are not expected to affect the bound (27). For
example, if $M=2$, then Ineq. (25) gives

$N_{P}\leq q+1+(d-1)(d-2)\sqrt{q}$ (28)

which is the Weil’s upper bound (6) for a smooth plane curve, whose geometric
genus $g$ is equal to $(d-1)(d-2)/2$. This inequality holds also for singular
curves aubry . Indeed, this comes from the upper bound (7) and the equality
$g=(d-1)(d-2)/2-\delta$. Also reducibility does not affect Ineq (27).

It is simple to find examples of multivariate functions with a number of
rational zero quite close to the bound $Kd^{2M}$. Trivially, there are
polynomials ${\cal N}(\tau_{1},\dots,\tau_{M})$ of degree $d$ with a number of
rational zeros at least equal to the number of coefficients minus $1$, that
is, equal to $\bar{N}_{P}\equiv M!^{-1}\prod_{k=1}^{M}(d+k)-1\sim
d^{M}/M!+O(d^{M-1})$. For $M=1$, this corresponds to take the univariate
polynomial

${\cal N}(\tau)=(\tau-x_{1})(\tau-x_{2})\dots(\tau-x_{d}).$ (29)

A better construction of a multivariate polynomial is a generalization of the
univariate polynomial in Eq. (29). Given linear functions
$L_{i,s}(\vec{\tau})$, the polynomial

$\tilde{P}=\sum_{i=1}^{M}\prod_{s=1}^{d}L_{i,s}(\vec{\tau})$

has generally a number of rational points $N_{P}$ at least equal to $d^{M}$,
which is the square root of the upper bound, up to a constant. For $d<4$ and
$M=2$, the number of rational zeros turns out to be infinite, since the genus
is smaller than $2$ (see Sec. II.3.1 for the case of infinite rational
points). A naive computation of $\tilde{P}(\vec{\tau})$ takes $dM^{2}$
arithmetic operations, that is, its complexity is polynomial in $M$. This
example provides an illustration of the complexity test described previously
in Claim 2. Expressing $d$ in terms of $M$ and $\xi=\log N_{P}$ and assuming
that ${\bf C}_{0}\sim dM^{2}$, we have that

${\bf C}_{0}(\xi)=M^{2}e^{M^{-1}\xi},$

which is subexponential in $\xi$ (provided that $M$ is a growing function of
$\xi$), which is a necessary condition for a subexponential algorithm.
However, the polynomial does not pass the litmus test, as ${\bf
C}_{0}(\xi)^{M}$ grows exponentially.

####  II.3.1 The case of infinite rational zeros

Until now, we have assumed that the rational function has a finite number of
rational zeros over the rationals. However, in the multivariate case, it is
possible to have non-zero functions with an infinite number of zeros. For
example, this is the case of a bivariate polynomials with genus equal to zero
and one, which correspond to parametrizable curves and elliptic curves,
respectively. We can also have functions whose zero locus contains linear
subspaces with positive dimension, which can have infinite rational points.
Since the probability of having ${\cal R}$ equal to zero modulo $p$ increases
with the number of zeros over the rationals, this would imply that the
probability is equal to $1$ if the number of zeros is infinite. This is not
evidently the case. For example, if ${\cal R}$ is zero for $x_{1}=0$ and
$M>1$, evidently the function has infinite rational points over $\mathbb{Q}$,
but the number of points with $x_{1}=0$ over $\mathbb{Z}_{p}$ is $p^{M-1}$,
which is $p$ times less than the number of points in the space. Once again, we
are interested more properly to sets of $N_{P}$ rational zeros over
$\mathbb{Q}$ such that a large fraction of them remain distinct over finite
fields whose order is greater than about $N_{P}^{1/M}$. Under this condition,
$N_{P}$ cannot be infinite and is constrained by Ineq. (27). If there are
linear subspaces with dimension $h>0$ in the zero locus of $\cal R$, we may
fix some of the parameters $\vec{\tau}$, so that these spaces become points.
In the next sections, we will build rational functions having isolated
rational points and possible linear subspaces in the zero locus. If there are
subspaces with dimension $k>0$ giving a dominant contribution to
factorization, we can transform them to isolated rational points by fixing
some parameters without changing the asymptotic complexity of the algorithm.
Isolated rational points are the only relevant points for an asymptotic study
of the complexity of the factoring algorithm, up to a dimension reduction.
Thus, we will consider only them and will not care of the other linear
subspaces.

##  III Setting the problem in the framework of algebraic geometry

Since the number of zeros $N_{P}$ is constrained by Ineq. (27), the complexity
of computing the rational function ${\cal R}(\vec{\tau})$ must be
subexponential or polynomial in $\log d$ in order to have ${\bf C}_{0}(\xi)$
subexponential or polynomial. This complexity scaling is attained if, for
example, $\cal R$ is a polynomial with few monomials. The univariate
polynomial $P=\tau^{d}-1$, which is pivotal in Pollard’s $p-1$ algorithm, can
be evaluated with a number of arithmetic operations scaling polynomially in
$\log d$. This is achieved by consecutively applying polynomial maps. For
example, if $d=2^{g}$, then $\tau^{d}$ is computed through $g$ applications of
the map $x\rightarrow x^{2}$ by starting with $x=\tau$. However, polynomials
with few terms have generally few zeros over $\mathbb{Q}$. More general
polynomials and rational functions with friendly computational complexity are
obviously available and are obtained by consecutive applications of simple
functions, as done for $\tau^{d}-1$. This leads us to formulate the
factorization problem in the framework of algebraic geometry as an
intersection problem.

###  III.1 Intersection points between a parametrizable variety and a
hypersurface

Considering only the operations defined in the field, the most general
rational functions ${\cal R}(\vec{\tau})$ with low complexity can be evaluated
through the consecutive application of a small set of simple rational
equations of the form

$\begin{array}[]{c}x_{n-M}=\frac{{\cal N}_{n-M}(x_{n-M+1},\dots,x_{n})}{{\cal
D}_{n-M}(x_{n-M+1},\dots,x_{n})}\\\ x_{n-M-1}=\frac{{\cal
N}_{n-M-1}(x_{n-M},\dots,x_{n})}{{\cal D}_{n-M-1}(x_{n-M},\dots,x_{n})}\\\
\vdots\\\ x_{1}=\frac{{\cal N}_{1}(x_{2},\dots,x_{n})}{{\cal
D}_{1}(x_{2},\dots,x_{n})}\\\ {\cal R}=P_{0}(x_{1},\dots,x_{n}),\end{array}$
(30)

where $P_{0}$ is a polynomial. If the numerators and denominators ${\cal
N}_{k}$ and ${\cal D}_{k}$ do not contain too many monomials, then the
computation of ${\cal N}_{k}/{\cal D}_{k}$ can be performed efficiently.
Assuming that the computational complexity of these rational functions is
polynomial in $n$, the complexity of $\cal R$ is polynomial in $n$. The
computation of ${\cal R}(\vec{\tau})$ is performed by setting the last $M$
components $x_{n-M+1},\dots,x_{n}$ equal to $\tau_{1},\dots,\tau_{M}$ and
generating the sequence $x_{n-M},x_{n-M-1},\dots,x_{1},{\cal R}$ according to
Eqs. (30), which ends up with the value of ${\cal R}$. The procedure may fail
to compute the right value of ${\cal R}(\vec{\tau})$ if some denominator
${\cal D}_{k}(\vec{\tau})\equiv{\cal
D}_{k}[x_{k+1}(\vec{\tau}),\dots,x_{n}(\vec{\tau})]$ turns out to be equal to
zero during the computation. However, since our only purpose is to generate
the zero of the field, we can take a zero divisor as outcome and stop the
computation of the sequence. In this way, the algorithm generates a modified
function ${\cal R}^{\prime}(\vec{\tau})$. Defining $\bar{\cal
N}_{k}(\vec{\tau})$ as the numerator of the rational function ${\cal
D}_{k}(\vec{\tau})$, we have

${\cal R}^{\prime}(\vec{\tau})=\left\\{\begin{array}[]{lr}{\cal
R}(\vec{\tau})&\;\;\text{if}\;\;\bar{\cal N}_{1}(\vec{\tau})\dots\bar{\cal
N}_{n-M}(\vec{\tau})\neq 0\\\ 0&\text{otherwise}\end{array}\right.$ (31)

The function ${\cal R}^{\prime}(\vec{\tau})$ has the zeros of ${\cal
N}(\vec{\tau})\bar{\cal N}_{1}(\vec{\tau})\dots\bar{\cal
N}_{n-M}(\vec{\tau})$. For later reference, let us define the following.

######  Algorithm 2.

Computation of ${\cal R}^{\prime}(\vec{\tau})$.

  1. 1.

set $(x_{n-M+1},\dots,x_{n})=(\tau_{1},\dots,\tau_{M})$;

  2. 2.

set $k=n-M>0$;

  3. 3.

set $x_{k}=\frac{{\cal N}_{k}(x_{k+1},\dots,x_{n})}{{\cal
D}_{k}(x_{k+1},\dots,x_{n})}$. If the division fails, return the denominator
as outcome;

  4. 4.

set $k=k-1$;

  5. 5.

if $k=0$, return $P_{0}(x_{1},\dots,x_{n})$, otherwise go back to 3.

The zeros of the denominators are not expected to give an effective
contribution on the asymptotic complexity of the factoring algorithm,
otherwise it would be more convenient to reduce the number of steps of the
sequence by one and replace the last function $P_{0}$ with the denominator
${\cal D}_{1}$. Let us show that. Let us denote by $N_{1}$ the number of
rational zeros of ${\cal R}^{\prime}$ over some finite field with all the
denominators different from zeros. They are the zeros returned at step 5 of
Algorithm 2. Let $N_{T}$ be the total number of zeros. We remind that the
factoring complexity is about $p^{kM}$ times the ratio between the complexity
of $\cal R$ and the number of zeros. If the algorithm is more effective than
the one with one step less and $P_{0}$ replaced with ${\cal D}_{1}$, then
$\frac{C_{T}}{N_{T}}<\frac{C_{T}-C_{1}}{N_{T}-N_{1}}$. where $C_{1}$ and
$C_{T}$ are the number of arithmetic operations of the last step and of the
whole algorithm, respectively. Since $C_{1}\geq 1$, we have

$N_{1}>N_{T}C_{T}^{-1}$

In order to have a subexponential factoring algorithm, $C_{T}$ must scale
subexponentially in $\log N_{T}$. Thus,

$N_{1}>N_{T}e^{-\alpha(\log N_{T})^{\beta}}$

for some positive $\alpha$ and $0<\beta<1$. That is,

$\log N_{1}>\log N_{T}-\alpha(\log N_{T})^{\beta}.$

If we assume polynomial complexity, we get the tighter bound

$\log N_{1}>\log N_{T}-\alpha\log\log N_{T}.$

These inequalities imply that the asymptotic complexity of the factoring
algorithm does not change if we discard the zero divisors at Step 3 in
Algorithm 2. Thus, for a complexity analysis, we can consider only the zeros
of ${\cal R}^{\prime}(\vec{\tau})$ with all the denominators ${\cal
D}_{k}(\vec{\tau})$ different from zero. This will simplify the subsequent
discussion. Each of these zeros are associated with an $n$-tuple
$(x_{1},\dots,x_{n})$, generated by Algorithm 2 and solutions of Eqs. (30).
Let us denote by ${\cal Z}_{P}$ the set of these $n$-tuples.

By definition, an element in ${\cal Z}_{P}$ is a zero of the set of $M-n+1$
polynomials

$\begin{array}[]{l}P_{0}(x_{1},\dots,x_{n}),\\\
P_{k}(x_{1},\dots,x_{n})=x_{k}{\cal D}_{k}(x_{k+1},\dots,x_{n})-{\cal
N}_{k}(x_{k+1},\dots,x_{n}),\;\;\;k\in\\{1,\dots,n-M\\}.\end{array}$ (32)

The last $n-M$ polynomials define an algebraic set of points, say $\cal A$,
having one irreducible branch parametrizable by Eqs. (30). This branch defines
an algebraic variety which we denote by $\cal V$. The algebraic set may have
other irreducible components which do not care about. The polynomial $P_{0}$
defines a hypersurface, say $\cal H$. Thus, the set ${\cal Z}_{P}$ is
contained in the intersection between $\cal V$ and $\cal H$. This intersection
may contain singular points of $\cal V$ with ${\cal
D}_{k}(x_{k+1},\dots,x_{n})=0$ for some $k$, which are not relevant for a
complexity analysis, as shown previously. Thus, the factorization problem is
reduced to search for non-singular rational points of a parametrizable variety
$\cal V$, whose intersection with a hypersurface $\cal H$ contains an
arbitrarily large number $N_{P}$ of rational points. If $N_{P}$ and ${\bf
C}_{0}$ scale exponentially and polynomially in the space dimension $n$,
respectively, then the complexity of factorization is polynomial, provided
that the number of parameters $M$ scales sublinearly as a power of $n$. In the
limit case of

$M\sim n/(\log n)^{\beta}$ (33)

with $\beta>1$, the complexity scales subexponentially as $e^{b(\log
p)^{1/\beta}}$. Thus, if $M$ has the scaling property (33) with $\beta>3$,
then there is an algorithm outperforming asymptotically the general number
field sieve. A subexponential computational complexity is also obtained if the
complexity of evaluating a point in $\cal V$ is subexponential.

The parametrization of $\cal V$ is a particular case of rational
parametrization of a variety. We call it _Gaussian parametrization_ since the
triangular form of the polynomials $P_{1},\dots,P_{n-M}$ resembles Gaussian
elimination. Note that this form is invariant under the transformation

$P_{k}\rightarrow
P_{k}+\sum_{k^{\prime}=k+1}^{n-M}\omega_{k,k^{\prime}}P_{k^{\prime}}.$ (34)

The form is also invariant under the variable transformation

$x_{k}\rightarrow
x_{k}+\sum_{k^{\prime}=k+1}^{n+1}\eta_{k,k^{\prime}}x_{k^{\prime}}$ (35)

with $x_{n+1}=1$.

It is interesting to note that if $N_{P}^{\prime}$ out of the $N_{P}$ points
in ${\cal Z}_{P}$ are collinear, then it is possible to build another variety
with Gaussian parametrization and a hypersurface over a $(n-1)$-dimensional
subspace such that their intersection contains the $N_{P}^{\prime}$ points.
For later reference, let us state the following.

######  Lemma 3.

Let ${\cal Z}_{P}$ be the set of common zeros of the polynomials (32) with
${\cal D}_{k}(x_{k+1},\dots,x_{n})\neq 0$ over ${\cal Z}_{P}$ for
$k\in\\{1,\dots,n-M\\}$. If $N_{P}^{\prime}$ points in ${\cal Z}_{P}$ are
solutions of the linear equation $L(x_{1},\dots,x_{n})=0$, then there is a
variety with Gaussian parametrization and a hypersurface over the
$(n-1)$-dimensional subspace defined by $L(x_{1},\dots,x_{n})=0$ such that
their intersection contains the $N_{P}^{\prime}$ points.

Proof. Given the linear function $L(x_{1},\dots,x_{n})\equiv
l_{n+1}+\sum_{k=1}^{n}l_{k}x_{k}$, let us first consider the case with
$l_{k}=0$ for $k\in\\{1,\dots,n-M\\}$. Using the constraint $L=0$, we can set
one of the $M$ variables $x_{n-M+1},\dots,x_{n}$ as a linear function of the
remaining $M-1$ variables. Thus, we get a new set of polynomials retaining the
original triangular form. The new parametrizable variety, say ${\cal
V}^{\prime}$, has $M-1$ parameters. The intersection of ${\cal V}^{\prime}$
with the new hypersurface over the $(n-1)$-dimensional space contains the
$N_{P}^{\prime}$ points. Let us now consider the case with $l_{k}=0$ for
$k\in\\{1,\dots,\bar{k}\\}$, where $\bar{k}$ is some integer between $0$ and
$n-M-1$, such that $l_{\bar{k}+1}\neq 0$. We can use the constraint $L=0$ to
set $x_{\bar{k}+1}$ as a linear function of $x_{\bar{k}+2},\dots,x_{n}$. We
discard the polynomial $P_{\bar{k}+1}$ and eliminate the $(\bar{k}+1)$-th
variable from the remaining polynomials. We get $n-1$ polynomials retaining
the original triangular form in $n-1$ variables
$x_{1},\dots,x_{\bar{k}},x_{{\bar{k}}+2},\dots,x_{n}$. The intersection
between the new parametrizable variety and the new hypersurface contain the
$N_{P}^{\prime}$ points $\square$.
This simple lemma will turn out to be a useful tool in different parts of the
paper.

In Section III.2, we show how to build a set of polynomials $P_{k}$ with a
given number $N_{P}$ of common rational zeros by using some tools of algebraic
geometry described in Appendix A. In Sec. IV, we close the circle by imposing
the form (32) for the polynomials $P_{k}$ with the constraint that ${\cal
D}_{k}(x_{k+1},\dots,x_{n})\neq 0$ for $k\in\\{1,\dots,n-M\\}$ over the set of
$N_{P}$ points.

###  III.2 Sets of polynomials with a given number of zeros over a number
field

In this subsection, we build polynomials with given $N_{P}$ common rational
zeros as elements of an ideal $I$ generated by products of linear functions.
This construction is the most general. The relevant information on the ideal
$I$ is summarized by a satisfiability formula in conjunctive normal form
without negations and a linear matroid. The formula and the matroid uniquely
determine the number $N_{P}$ of rational common zeros of the ideal.
Incidentally, we also show that the information can be encoded in a more
general formula with negations by a suitable choice of the matroid.

Every finite set of points in an $n$-dimensional space is an algebraic set,
that is, they are all the zeros of some set of polynomials. More generally,
the union of every finite set of linear subspaces is an algebraic set. In the
following, we will denote linear polynomials by a symbol with a hat; namely,
$\hat{a}$ is meant as $a_{n+1}+\sum_{i=1}^{n}a_{i}x_{i}$. Let us denote by
$\vec{x}$ the $(n+1)$-dimensional vector $(x_{1},\dots,x_{n},x_{n+1})$, where
$x_{n+1}$ is an extra-component that is set equal to $1$. A linear polynomial
$\hat{a}$ is written in the form $\vec{a}\cdot\vec{x}$. Let
$V_{1},\dots,V_{L}$ be a set of linear subspaces and $I_{1},\dots,I_{L}$ their
associated radical ideals. The codimension of the $k$-th subspace is denoted
by $n_{k}$. The minimal set of generators of the $k$-th ideal contains $n_{k}$
independent linear polynomials, say $\hat{a}_{k,1},\dots,\hat{a}_{k,n_{k}}$,
so that

$\vec{x}\in V_{k}\Leftrightarrow\vec{a}_{k,i}\cdot\vec{x}=0\;\;\forall
i\in\\{1,\dots,n_{k}\\}.$ (36)

If the codimension $n_{k}$ is equal to $n$, then $V_{k}$ contains one point.
We are mainly interested to these points, whose number is taken equal to
$N_{P}$. The contribution of higher dimensional subspaces to the asymptotic
complexity of the factoring algorithm is irrelevant up to a dimension
reduction (see also Sec. II.3.1 and the remark in the end of the section).
Since only isolated points are relevant, we could just consider ideals whose
zero loci contain only isolated points. However, we allow for the possible
presence of subspaces with positive dimension since they may simplify the set
of the generators or the form of the polynomials $P_{k}$ that eventually we
want to build.

Let $\cal Z$ be the union of the subspaces $V_{k}$. The product $I_{1}\cdot
I_{2}\cdot\dots I_{L}\equiv\tilde{I}$ is associated with $\cal Z$, that is,
${\cal Z}={\bf V}(\tilde{I})$. A set of generators of the ideal $\tilde{I}$ is

$\prod_{k=1}^{L}\hat{a}_{k,i_{k}}\equiv
G_{i_{1},\dots,i_{L}}(\vec{x})\;\;\;i_{r}\in\\{1,\dots,n_{r}\\},r\in\\{1,\dots,L\\}.$
(37)

Thus, we have that

$\vec{x}\in{\cal Z}\Leftrightarrow
G_{i_{1},\dots,i_{L}}(\vec{x})=0\;\;\;\;i_{r}\in\\{1,\dots,n_{r}\\},r\in\\{1,\dots,L\\}.$
(38)

Polynomials in the ideal $\tilde{I}$ are zero in the set $\cal Z$. This
construction is not the most general, as $\tilde{I}$ is not radical. Thus,
there are polynomials that are not in $\tilde{I}$, but their zero locus
contains $\cal Z$. Furthermore, the number of generators and the number of
their factors grow polynomially and linearly in $N_{P}$, respectively. This
makes it hard to build polynomials in $\tilde{I}$ whose complexity is
polynomial in $\log N_{P}$. The radicalization of the ideal and the assumption
of special arrangements of the subspaces in $\cal Z$ can reduce drastically
both the degree of the generators and their number. For example, let us assume
that $V_{1}$ and $V_{2}$ are two isolated points in the $n$-dimensional space
and, thus, $n_{1}=n_{2}=n$. The overall number of generators
$a_{1,1},\dots,a_{1,n}$ and $a_{2,1},\dots,a_{2,n}$ is equal to $2n$. Thus,
there are $n-1$ linear constraints among the generators. Using linear
transformations, we can write these constraints as

$\hat{a}_{1,i}=\hat{a}_{2,i}\equiv\hat{a}_{i}\;\;\;\forall
i\in\\{2,\dots,n\\}.$

Every generator $G_{i,i,i_{3},\dots,i_{L}}$ with $i\neq 1$ is equal to
$\bar{G}_{i,i_{3},\dots,i_{L}}=a_{i}^{2}\prod_{k=3}^{L}\hat{a}_{k,i_{k}}$. The
polynomial $\bar{G}^{\prime}_{i,i_{3},\dots,i_{L}}\equiv
a_{i}\prod_{k=3}^{L}\hat{a}_{k,i_{k}}$ is not an element of the ideal
$\tilde{I}$, but it is an element of its radical. Indeed, it is zero in the
algebraic set $\cal Z$. Thus, we extend the ideal by adding these new
elements. This extension allows us to eliminate all the generators
$G_{i_{1},i_{2},\dots,i_{L}}$ with $i_{1}=1$ or $i_{2}=1$, since they are
generated by $\bar{G}^{\prime}_{i,i_{3},\dots,i_{L}}$. Thus, the new ideal has
the generators,

$\left.\begin{array}[]{l}\hat{a}_{1,1}\hat{a}_{2,1}\prod_{k=3}^{L}a_{k,i_{k}}\\\
\hat{a}_{i}\prod_{k=3}^{L}a_{k,i_{k}},\;\;\;i\in\\{2,\dots,n\\}\end{array}\right\\}i_{r}\in\\{1,\dots,n_{r}\\},r\in\\{3,\dots,L\\}.$
(39)

Initially, we had $n^{2}\prod_{k=3}^{L}n_{k}$ generators. Now, their number is
$n\prod_{k=3}^{L}n_{k}$. A large fraction of them has the degree reduced by
one. We can proceed with the other points and further reduce both degrees and
number of generators. Evidently, this procedure cannot take to a drastic
simplification of the generators if the points in $\cal Z$ are in general
position, since the generators must contain the information about these
positions. A simplification is possible if the points have special
arrangements taking to contraction of a large number of factors in the
generators. Namely, coplanarity of points is the key feature that can take to
a drastic simplification of the generators. In a $n$-dimensional space, there
are at most $n$ coplanar points in general position. Let us consider algebraic
sets containing larger groups of coplanar points. For example, let us assume
that the first $m$ sets $V_{1},\dots,V_{m}$ are distinct coplanar points, with
$m\gg n$. Then, there is a vector $\vec{a}_{1}$ such that
$\vec{a}_{1}\cdot\vec{x}=0$ for every $\vec{x}$ in the union of the first $m$
linear spaces. It is convenient to choose the linear polynomial
$\vec{a}_{1}\cdot\vec{x}$ as common generator of the first $m$ ideals
$I_{1},\dots,I_{m}$. Let us set $\hat{a}_{k,1}=\hat{a}_{1}$ for
$k\in\\{1,\dots,m\\}$. Every generator $G_{i_{1},\dots,i_{L}}$ with $i_{k}=1$
for some $k\in\\{1,\dots,m\\}$ is contracted to a generator of the form
$\hat{a}\prod_{k=m+1}^{L}\hat{a}_{k,i_{k}}$. If there are other groups of
coplanar points, we can perform other contractions.

######  Definition 1.

Given an integer ${\bar{n}}>n$, we define $\Gamma_{s}$ with
$s\in\\{1,\dots,{\bar{n}}\\}$ as a set of $s$-tuples
$(i_{1},\dots,i_{s})\in\\{1,\dots,{\bar{n}}\\}^{s}$ with
$i_{k}<i_{k^{\prime}}$ for $k<k^{\prime}$. That is,

$\forall
s\in\\{1,\dots,{\bar{n}}\\},\;\;\;\Gamma_{s}\subseteq\\{(i_{1},\dots,i_{s})\in\\{1,\dots,{\bar{n}}\\}^{s}|i_{k}<i_{k^{\prime}},\forall
k,k^{\prime}\text{ s.t. }k<k^{\prime}\\}.$ (40)

The final result of the inclusion of elements of the radical ideal is another
ideal, say $I$, with generators of the form

$\begin{array}[]{l}\hat{a}_{i_{1}}\;\;\;\forall i_{1}\in\Gamma_{1}\\\
\hat{a}_{i_{1}}\hat{a}_{i_{2}}\;\;\;\forall(i_{1},i_{2})\in\Gamma_{2}\\\
\dots\\\
\hat{a}_{i_{1}}\hat{a}_{i_{2}}\dots\hat{a}_{i_{{\bar{n}}}}\;\;\;\forall(i_{1},i_{2},\dots,i_{{\bar{n}}})\in\Gamma_{{\bar{n}}},\end{array}$
(41)

where $\\{\hat{a}_{1},\dots,\hat{a}_{{\bar{n}}}\\}\equiv\Phi$ is a set of
${\bar{n}}$ linear polynomials. Polynomials in this form generate the most
general ideals whose zero loci contain a given finite set of points. This is
formalized by the following.

######  Lemma 4.

Every radical ideal associated with a finite set ${\cal Z}_{P}$ of points is
generated by a set of polynomials of form (41) for some $\bar{n}$.

Proof. This can be shown with a naive construction. Given a set $\bar{S}$ of
$N_{P}$ points associated with the ideals $I_{1},\dots,I_{N_{P}}$, the product
$I_{1}\cdot\dots I_{N_{P}}$ is an ideal associated with the set $\bar{S}$,
which can be radicalized by adding a certain number of univariate square-free
polynomials as generators seidenberg . The resulting ideal is generated by a
set of polynomials of form (41). $\square$
With the construction used in the proof, $\bar{n}$ ends up to be equal to the
number of points in ${\cal Z}_{P}$, which is not optimal for our purposes. We
are interested to keep $\bar{n}$ sufficiently small, possibly scaling
polynomially in the dimension $n$. This is possible only if the points in the
zero locus have a ‘high degree’ of collinearity. Thus, a bound on $\bar{n}$
sets a restriction on ${\cal Z}$.

The minimal information on $\Phi$ that is relevant for determining the number
$N_{P}$ of points in $\cal Z$ is encoded in a linear _matroid_ , of which
$\Phi$ is one linear representation. Thus, the sets $\Gamma_{s}$ and the
matroid determine $N_{P}$. Note that the last set $\Gamma_{{\bar{n}}}$ has at
most one element. The linear generators can be eliminated by reducing the
dimension of the affine space, see Lemma 3. Thus, we can set
$\Gamma_{1}=\emptyset$. Every subset $\Phi_{sub}$ of $\Phi$ is associated with
a linear space $V_{sub}$ whose points are the common zeros of the linear
functions in $\Phi_{sub}$. That is, $V_{sub}={\bf V}(I_{sub})$, where
$I_{sub}$ is the ideal generated by $\Phi_{sub}$. Let us denote briefly by
${\bf V}(\Phi_{sub})$ the linear space ${\bf V}(I_{sub})$. This mapping from
subsets of $\Phi$ to subspaces is not generally injective. Let
$\hat{a}^{\prime}\in\Phi\setminus\Phi_{sub}$ be a linear superposition of the
functions in $\Phi_{sub}$, then $\Phi_{sub}$ and
$\Phi_{sub}\cup\\{\hat{a}^{\prime}\\}$ represent the same linear space. An
injective mapping is obtained by considering only the maximal subset
associated with a linear subspace. These maximal subsets are called _flats_ in
matroid theory.

######  Definition 2.

_Flats_ of the linear matroid $\Phi$ are defined as subsets
$\Phi_{sub}\subseteq\Phi$ such that no function in $\Phi\setminus\Phi_{sub}$
is linearly dependent on the functions in $\Phi_{sub}$.

Let us also define the closure of a subset of $\Phi$.

######  Definition 3.

Given a subset $\Phi_{sub}$ of $\Phi$ associated with subspace $V$, its
closure $\text{cl}(\Phi_{sub})$ is the flat associated with $V$.

The number of independent functions in a flat is called _rank_ of the flat.
The whole set $\Phi$ is a flat of rank $n+1$, which is associated with an
empty space. Flats of rank $n$ define points of the $n$-dimensional affine
space (with $x_{n+1}=1$). More generally, flats of rank $k$ define linear
spaces of dimension $n-k$. The dimension of a flat $\Phi_{flat}$ is meant as
the dimension of the space ${\bf V}(\Phi_{flat})$.

The structure of the generators (41) resembles a Boolean satisfiability
problem (SAT) in conjunctive normal form without negations. Let us interpret
$\hat{a}_{i}$ as a logical variable $a_{i}$ which is true or false if the
function is zero or different from zero, respectively. Every subset
$\Phi_{sub}\subseteq\Phi$ is identified with a string
$(a_{1},\dots,a_{{\bar{n}}})$ such that $a_{i}=\emph{true}$ if and only if
$\hat{a}_{i}\in\Phi_{sub}$.

The SAT formula associated with the generators (41) is

$\bigwedge\limits_{k=2}^{{\bar{n}}}\left(\bigvee\limits_{i\in\Gamma_{k}}a_{i}\right).$
(42)

Given a flat $\Phi_{flat}$, the linear space ${\bf V}(\Phi_{flat})$ is a
subset of $\cal Z$ if and only if $\Phi_{flat}$ is solution of the SAT
formula. If a set $\Phi_{sub}\subseteq\Phi$ is solution of the SAT formula,
then the flat $\text{cl}(\Phi_{sub})$ is also solution of the formula. Thus,
satisfiability implies that there are flats as solutions of the formula. This
does not mean that satisfiability implies that $\cal Z$ is non-empty. Indeed,
if the dimension of ${\bf V}(\Phi_{sub})$ is negative for every solution
$\Phi_{sub}$, then the set $\Phi$ is the only flat solution of the formula. We
are interested to the isolated points in $\cal Z$. A point $p\in{\cal Z}$ is
_isolated_ if there is a SAT solution $\Phi_{flat}$ with zero dimension such
that $p\in{\bf V}(\Phi_{flat})$ and no flat
$\Phi_{flat}^{\prime}\subset\Phi_{flat}$ is solution of the Boolean formula.
We denote by ${\cal Z}_{P}$ the subset in $\cal Z$ containing the isolated
points. Since the number $N_{P}$ of isolated points is completely determined
by the SAT formula and the linear matroid, the information on these two latter
objects is the most relevant. Given them, the linear functions $\hat{a}_{i}$
have some free coefficients.

Remark. In general, we do not rule out sets $\cal Z$ containing subspaces with
positive dimension, however these subspaces are irrelevant for the complexity
analysis of the factoring algorithm. For example, if subspaces of dimension
$d_{s}<M$ give a dominant contribution to factorization, then we can generally
eliminate $d_{s}$ out of the $M$ parameters by setting them equal to
constants, so that the subspaces are reduced to points. Furthermore, subspaces
with dimension greater than $M-1$ are not in the parametrizable variety $\cal
V$, whose dimension is $M$. Neither the overall contribution of all the
subspaces with positive dimension can provide a significant change in the
asymptotic complexity up to parameter deletions. Thus, only isolated points of
$\cal Z$ are counted without loss of generality.

###  III.3 Boolean satisfiability and algebraic-set membership

As we said previously, the Boolean formula does not encode all the information
about the number of isolated points in ${\cal Z}$, which also depends on the
independence relations among the vectors $\vec{a}_{i}$, specified by the
matroid. A better link between the SAT problem and the membership to ${\cal
Z}$ can be obtained if we consider sets $\Phi$ with cardinality equal to $2n$
and interpret half of the functions in $\Phi$ as negations of the others. Let
us denote by $\hat{a}_{0,1},\dots,\hat{a}_{0,n}$ and
$\hat{a}_{1,1},\dots,\hat{a}_{1,n}$ the $2n$ linear functions of $\Phi$. For
general functions, we have the following.

######  Property 2.

The set of vectors
$\\{\vec{a}_{s_{1},1},\dots,\vec{a}_{s_{n},n},\vec{a}_{1-s_{k},k}\\}$ is
independent for every string $\vec{s}=(s_{1},\dots,s_{n})\in\\{0,1\\}^{n}$ and
every $k\in\\{1,\dots,n\\}$.

This property generally holds if the functions are picked up at random. Let us
assume that $\Phi$ satisfies Property 2. This implies that
$\\{\hat{a}_{s_{1},1},\dots,\hat{a}_{s_{n},n}\\}$ are linearly independent and
equal to zero at one point $\vec{x}_{\vec{s}}$. Furthermore, Property 2 also
implies that different strings $\vec{s}$ are associated with different points
$\vec{x}_{\vec{s}}$.

######  Lemma 5.

Let
$\\{\vec{a}_{0,1},\dots,\vec{a}_{0,n},\vec{a}_{1,1},\dots,\vec{a}_{1,n}\\}$ be
a set of $2n$ vectors satisfying Property 2. Let $\vec{x}_{\vec{s}}$ be the
solution of the equations $\hat{a}_{s_{1},1}=\dots=\hat{a}_{s_{n},n}=0$. If
$\vec{s}\neq\vec{r}$, then $\vec{x}_{\vec{s}}\neq\vec{x}_{\vec{r}}$.

Proof. Let us assume that $\vec{x}_{\vec{s}}=\vec{x}_{\vec{r}}$ with
$\vec{s}\neq\vec{r}$. There is an integer $k\in\\{1,\dots,n\\}$ such that
$s_{k}\neq r_{k}$. Thus, the set of vectors
$\\{\vec{a}_{s_{1},1},\dots,\vec{a}_{s_{n},n},\vec{a}_{1-s_{k},k}\\}$ are
orthogonal to $\vec{x}_{\vec{s}}$. Since the dimension of the vector space is
$n+1$, the set of $n+1$ vectors are linearly dependent, in contradiction with
the hypotheses. $\square$

Now, let us define the set ${\cal Z}$ as the zero locus of the ideal
generators

$\begin{array}[]{l}\hat{a}_{0,i}\hat{a}_{1,i}\;\;\;\forall
i\in\\{1,\dots,n\\}\\\
\hat{a}_{s_{1},i_{1}}\hat{a}_{s_{2},i_{2}}\;\;\;\forall(s_{1},i_{1};s_{2},i_{2})\in\Gamma_{2}\\\
\dots\\\
\hat{a}_{s_{1},i_{1}}\hat{a}_{s_{2},i_{2}}\dots\hat{a}_{s_{n},i_{n}}\;\;\;\forall(s_{1},i_{1};s_{2},i_{2},\dots,s_{n},i_{n})\in\Gamma_{n}.\end{array}$
(43)

The first $n$ generators provide an interpretation of $\hat{a}_{1,i}$ as
negation of $\hat{a}_{0,i}$, as consequence of Property 2. The $i$-th
generator implies that $(a_{0,i},a_{1,i})$ is equal to
$(\emph{true},\emph{false})$, $(\emph{false},\emph{true})$ or
$(\emph{true},\emph{true})$. However, the last case is forbidden by Property
2. Assume that $(a_{0,i},a_{1,i})$ is equal to $(\emph{true},\emph{true})$ for
some $i$. Then, there would be $n+1$ functions
$\hat{a}_{s_{1},1},\dots,\hat{a}_{s_{n},n},\hat{a}_{1-s_{i},i}$ equal to zero,
which is impossible since they are independent. Thus, the algebraic set
defined by the first $n$ generators contains $2^{n}$ distinct points, as
implied by Lemma 5, which are associated with all the possible states taken by
the logical variables. The remaining generators set further constraints on
these variables and define a Boolean formula in conjunctive normal form. With
this construction there is a one-to-one correspondence between the points of
the algebraic set ${\cal Z}$ and the solutions of the Boolean formula.

There is a generalization of the generators (43) that allows us to weaken
Property 2 while retaining the one-to-one correspondence. Let
$R_{1},\dots,R_{m}$ be $m$ disjoint non-empty sets such that
$\cup_{k=1}^{m}R_{k}=\\{1,\dots,n\\}$.

######  Property 3.

The set of vectors $\cup_{k=1}^{m}\\{\vec{a}_{s_{k},i}|i\in R_{k}\\}\equiv
A_{\vec{s}}$ is independent for every
$\vec{s}=(s_{1},\dots,s_{m})\in\\{0,1\\}^{m}$. Furthermore, every vector
$\vec{a}_{s,i}\notin A_{\vec{s}}$ is not in $\text{span}(A_{\vec{s}})$, with
$s\in\\{0,1\\}$ and $i\in\\{1,\dots,n\\}$.

######  Lemma 6.

Let
$\\{\vec{a}_{0,1},\dots,\vec{a}_{0,n},\vec{a}_{1,1},\dots,\vec{a}_{1,n}\\}$ be
a set of $2n$ vectors satisfying Property 3. Let $\vec{x}_{\vec{s}}$ be the
solution of the equations

$\hat{a}_{s_{k},i}=0\;\;\;i\in R_{k},k\in\\{1,\dots,m\\}$

for every $\vec{s}\in\\{0,1\\}^{m}$. If $\vec{s}\neq\vec{r}$, then
$\vec{x}_{\vec{s}}\neq\vec{x}_{\vec{r}}$.

The generators (43) are generalized by replacing the first line with

$\hat{a}_{0,i}\hat{a}_{1,j},\;\;\;(i,j)\in\cup_{k=1}^{m}(R_{k}\times R_{k}).$
(44)

Provided that Property 3 holds there is a one-to-one correspondence between
the points in the algebraic set and the solutions of a SAT formula built
according to the following interpretation. Each set of functions
$\\{\hat{a}_{0,i}|i\in R_{k}\\}\equiv a_{k}$ is interpreted as a Boolean
variable, which is true if the functions in there are equal to zero. The set
$\\{\hat{a}_{1,i}|i\in R_{k}\\}$ is interpreted as negation of
$\\{\hat{a}_{0,i}|i\in R_{k}\\}$. The SAT formula is built in obvious way from
the set of generators. For example, the generator $\hat{a}_{0,i}\hat{a}_{0,j}$
with $i\in R_{1}$ and $j\in R_{2}$ induces the clause $a_{1}a_{2}$. Different
generators can induce the same clause. Since the total number of solutions
depends only on the SAT formula, it is convenient to take the maximal set of
generators compatible with a given formula. That is, if $a_{1}a_{2}$ is a
clause, then $\hat{a}_{0,i}\hat{a}_{0,j}$ is taken as a generator for every
$i\in R_{1}$ and $j\in R_{2}$.

###  III.4 $3$SAT-like generators

SAT problems have clauses with an arbitrarily large number of literals.
Special cases are $2$SAT and $3$SAT, in which clauses have at most $2$ or $3$
literals. It is known that every SAT problem can be converted to a $3$SAT one
by increasing the number of variables and replacing a clause with a certain
number of smaller clauses containing the new variables. For example, the
clause $a\lor b\lor c\lor d$ can be replaced by $a\lor b\lor x$ and $c\lor
d\lor(\lnot x)$. An assignment satisfies the first clause if and only if the
other two clauses are satisfied for some $x$. An identical reduction can be
performed also on the generators (41). For example, a generator in $I$ of the
form $\hat{a}_{1}\hat{a}_{2}\hat{a}_{3}\hat{a}_{4}\equiv G_{0}$ can be
replaced by $\hat{a}_{1}\hat{a}_{2}y\equiv G_{1}$,
$\hat{a}_{1}\hat{a}_{2}(1-y)\equiv G_{2}$ and $y(1-y)\equiv G_{3}$, where $y$
is an additional variable. Also in this case, $G_{0}$ is equal to zero if and
only if $G_{1}$ and $G_{2}$ are zero for $y=0,1$. Furthermore, the new
extended ideal contains the old one. Indeed, we have that
$G_{0}=\hat{a}_{3}\hat{a}_{4}G_{1}+\hat{a}_{1}\hat{a}_{2}G_{2}$.

Note that all the polynomials in the ideal $I$ are independent of the
additional variables used in the reduction. Thus, if we build the polynomials
(32) by using $3$SAT-like generators, then all these polynomials may be
independent of some variables. Thus, we can consider generators in a $3$SAT
form,

$\begin{array}[]{l}\hat{a}_{i_{1}}\hat{a}_{i_{2}}\;\;\;\forall(i_{1},i_{2})\in\Gamma_{2}\\\
\hat{a}_{i_{1}}\hat{a}_{i_{2}}\hat{a}_{i_{3}}\;\;\;\forall(i_{1},i_{2},i_{3})\in\Gamma_{3}.\end{array}$
(45)

There is no loss of generality, provided that all the polynomials $P_{k}$ are
possibly independent from $n_{I}$ variables.

The number of isolated points satisfies the inequality

$N_{P}\leq 3^{n}.$ (46)

The actual number can be considerably smaller, depending on the matroid and
the number of clauses defining the Boolean formula. The bound is attained if
$n_{c}=3n$, the generators have the form $a_{i}b_{i}c_{i}$ with
$i\in\\{1,\dots,n\\}$, and the independent sets of the matroid contain $n+1$
elements. If there are only clauses with $2$ literals, then the bound is

$N_{P}\leq 2^{n},$ (47)

which is strict if the generators have the form $a_{i}b_{i}$ with
$i\in\\{1,\cdots,n\\}$. A consequence of these constraints is that the number
$M$ of parameters must scale sublinearly in $n$,

$M\leq Kn^{\beta},\;\;\;\;0\leq\beta<1$ (48)

for some $K>0$.

##  IV Building up the parametrizable variety and the hyperplane

In this section, we put together the tools introduced previously to tackle our
problem of building the rational function ${\cal R}$ with the desired
properties of being computationally simple and having a sufficiently large set
of zeros. This problem has being reduced to the search of computationally
simple polynomials $P_{k}$ of the form (32) with a number of common rational
zeros growing sufficiently fast with the space dimension. To build these
polynomials, we first choose a set of generators of the form (41) such that
the associated algebraic set $\cal Z$ has a set of $N_{P}$ points. Then, we
write the polynomials $P_{k}$ as elements of the ideal associated with $\cal
Z$. Finally, we impose that the polynomials $P_{k}$ have the form of Eqs.
(32).

######  Procedure 1.

Building up of a parametrizable variety $\cal V$ with $M$ parameters and
$N_{P}$ intersection points.

  1. 1.

Take a set of ${\bar{n}}$ unknown non-homogeneous linear functions in $n$
variables with ${\bar{n}}>n$, say $\hat{a}_{1},\dots,\hat{a}_{{\bar{n}}}$.
Additionally, specify which set of vectors are linearly independent. In other
words, a linear matroid with ${\bar{n}}$ elements is defined.

  2. 2.

Choose and ideal $I$ with generators of the form (45) such that the associated
algebraic set $\cal Z$ contains a subset ${\cal Z}_{P}$ of $N_{P}$ isolated
points over some given number field.

  3. 3.

Set the polynomials $P_{s}$ equal to elements of the ideal $I$ with
$s\in\\{0,\dots,n-M\\}$. That is,

$P_{s}(\vec{x})=\sum_{(i,j)\in\Gamma_{2}}C_{s,i,j}(\vec{x})\hat{a}_{i}\hat{a}_{j}+\sum_{(i,j,k)\in\Gamma_{3}}D_{s,i,j,k}(\vec{x})\hat{a}_{i}\hat{a}_{j}\hat{a}_{k},$
(49)

The polynomials $P_{s}$ with $s\in\\{1,\dots,n-M\\}$ define an algebraic set
$\cal A$. The polynomial $P_{0}$ defines a hyperplane $\cal H$. The number of
parameters $M$ and the polynomial coefficients $C_{s,i,j}(\vec{x})$ and
$D_{s,i,j,k}(\vec{x})$ are also unknown.

  4. 4.

Search for values of the coefficients such that there is a parametrizable
branch $\cal V$ in $\cal A$ with a number of parameters as small as possible.
All the polynomials $P_{s}$ with $s\in\\{0,\dots,n-M\\}$ are possibly
independent of some subset of variables (see Sec. III.4). The polynomials
${\cal D}_{k}$, as defined in Eq. (32) must be different from zero in the set
${\cal Z}_{P}$.

More explicitly, the last step leads us to the following.

######  Problem 1.

Given the sets $\Gamma_{2}$ and $\Gamma_{3}$, and polynomials of the form
(49), find linear functions $\hat{a}_{1},\dots,\hat{a}_{{\bar{n}}}$ and
coefficients $C_{s,i,j}(\vec{x})$, $D_{s,i,j,k}(\vec{x})$ such that

$\begin{array}[]{l}\frac{\partial P_{s}}{\partial x_{k}}=0,\;\;\;\;1\leq
k<s\leq n-M,\vspace{2mm}\\\ \frac{\partial^{2}P_{s}}{\partial
x_{s}^{2}}=0,\;\;\;\;1\leq s\leq n-M,\vspace{2mm}\\\ \vec{x}\in{\cal
Z}_{P}\Rightarrow\frac{\partial P_{s}}{\partial x_{s}}\equiv{\cal
D}_{s}(x_{s+1},\dots,x_{n})\neq 0,\end{array}$ (50)

under the constraint that $(\hat{a}_{1},\dots,\hat{a}_{{\bar{n}}})$ is the
representation of a given matroid.

Remark. If the algebraic set associated with the ideal $I$ is zero-
dimensional, this problem has always a solution for any $M$, since a rational
univariate representation always exists (see introduction). Essentially, the
task is to find ideals such that there is a solution with the coefficients
$C_{s,i,j}(\vec{x})$ and $D_{s,i,j,k}(\vec{x})$ as simple as possible, so that
their computation is efficient, given $\vec{x}$.

Let us remind that the constraints (50) are invariant under transformations
(34,35). All the polynomials are possibly independent of a subset of $n_{I}$
variables, say $\\{x_{n-n_{I}+1},\dots,x_{n}\\}$,

$\frac{\partial P_{s}}{\partial
x_{k}}=0,\;\;\;\;\left\\{\begin{array}[]{l}s\in\\{0,\dots,n-M\\}\\\
k\in\\{n-n_{I}+1,\dots,n\\}\end{array}\right.$ (51)

These $n_{I}$ variables can be set equal to constants, so that the actual
number of significant parameters is $M-n_{I}$. The input of Problem 1 is given
by a 3SAT formula of form (45) and a linear matroid.

######  Definition 4.

A 3SAT formula of form (45) and a linear matroid with $\bar{n}$ elements is
called a _model_.

In literature, the term ‘model’ is occasionally used with a different meaning
and refers to a solution of a SAT formula.

Problem 1 in its general form is quite intricate. First, it requires the
definition of a linear matroid and a SAT formula with an exponentially large
number of solutions associated with isolated points. Whereas it is easy to
find examples of matroids and Boolean formulas with this feature, it is not
generally simple to characterize models with an exponentially large number of
isolated points. Second, Eqs. (50) take to a large number of polynomial
equations in the unknown coefficients. Lemma 3 can help to reduce the search
space by dimension reduction. This will be shown in Sec. IV.2 with a simple
example. A good strategy is to start with simple models and low-degree
coefficients in Eq. (49). In particular, we can take the coefficients
constant, as done later in Sec. V. This restriction does not guarantees that
Problem 1 has a solution for a sufficiently small number of parameters $M$,
but we can have some hints on how to proceed.

###  IV.1 Required number of rational points vs space dimension

Let assume that the computational complexity ${\bf C}_{0}$ of $\cal R$ is
polynomial in the space dimension $n$, that is,

${\bf C}_{0}\sim n^{\alpha_{0}}.$ (52)

The factoring algorithm has polynomial complexity if

$\left.\begin{array}[]{l}K_{1}n^{\alpha}\leq\log N_{P}\leq
K_{2}n\;\;\;0<\alpha\leq 1\\\ M\leq(\log
N_{P})^{\beta}\;\;\;\beta<1\end{array}\right\\}\;\;\;(\text{polynomial
complexity})$ (53)

for $n$ sufficiently great, where $K_{1}$ is some positive constant and
$K_{2}=\log 3$. The upper bound is given by Eq. (46). The algorithm has
subexponential complexity ${\bf C}\sim e^{b(\log N_{P})^{\alpha}}$ with
$0<\alpha<1$ if

$\left.\begin{array}[]{r}\log N_{P}\sim(\log n)^{1/\alpha}\;\;\;0<\alpha<1,\\\
M\sim(\log
n)^{\frac{\beta}{\alpha}}\;\;\;0\leq\beta<1-\alpha.\end{array}\right\\}\;\;\;\;(\text{subexponential
complexity})$ (54)

The upper bound on $\beta$ comes from Lemma 2. Thus, the number of rational
points is required to scale much less than exponentially for getting
polynomial or subexponential factoring complexity. Note that a slower increase
of $N_{P}$ induces stricter bounds on $M$ in terms of $n$.

###  IV.2 Reduction of models

In this subsection, we describe an example of model reduction. The model
reduction is based on Lemma 3 and can be useful for simplifying Problem 1. The
task is to reduce a class of models associated with an efficient factoring
algorithm to a class of simpler models taking to another efficient algorithm,
so that it is sufficient to search for solutions of Problem 1 over the latter
smaller class.

In our example, the matroid contains $2n$ elements and is represented by the
functions
$\hat{a}_{0,1},\dots,\hat{a}_{0,n},\hat{a}_{1,1},\dots,\hat{a}_{1,n}$
satisfying Property 2.
Model A.
Matroid with representation
$(\hat{a}_{0,1},\dots,\hat{a}_{0,n},\hat{a}_{1,1},\dots,\hat{a}_{1,n})$
satisfying Property 2.
Generators:

$\begin{array}[]{l}\hat{a}_{0,i}\hat{a}_{1,i}\;\;\;i\in\\{1,\dots n\\}\\\
\hat{a}_{0,i}\hat{a}_{0,j}\;\;\;(i,j)\in\Gamma.\end{array}$ (55)

######  Definition 5.

A diagonal model is defined as Model A with $\Gamma=\emptyset$.

Clearly, an diagonal model defines an algebraic set with $2^{n}$ isolated
points. Each point satisfies the linear equations

$\hat{a}_{s_{i},i}=0,\;\;\;i\in\\{1,\dots,n\\}$ (56)

for some $(s_{1},\dots,s_{n})\in\\{0,1\\}^{n}$.

If there is an algorithm with polynomial complexity and associated with Model
A, then it is possible to prove that there is another algorithm with
polynomial complexity and associated with a diagonal model. More generally,
this formula reduction takes to a subexponential factoring algorithm, provided
that the parent algorithm outperforms the quadratic sieve algorithm. If the
parent algorithm outperforms the general number field sieve, then the reduced
algorithm outperforms the quadratic sieve. Thus, if we are interested to find
a competitive algorithm from Model A, we need to search only the space of
reduced formulas. If there is no algorithm outperforming the quadratic sieve
with $\Gamma=\emptyset$, then there is no algorithm outperforming the general
number field for $\Gamma\neq\emptyset$.

######  Theorem 1.

If there is a factoring algorithm with subexponential asymptotic complexity
$e^{a(\log p)^{\gamma}}$ and associated with Model A, then there is another
algorithm associated with the diagonal model with computational complexity
upper-bounded by the function $e^{\bar{a}(\log p)^{\frac{\gamma}{1-\gamma}}}$
for some $\bar{a}>0$. In particular, if the first algorithm has polynomial
complexity, also the latter has polynomial complexity.

Proof. Let us assume that the asymptotic computational complexity of the
parent algorithm is $e^{a(\log p)^{\gamma}}$. For every $N_{P}$, there is a
Model A with $N_{P}$ isolated points and generating a rational function ${\cal
R}$ with complexity ${\bf C}_{0}(\xi)$ scaling as $e^{a(\log N_{P})^{\alpha}}$
and a number of parameters $M$ scaling as $(\log N_{P})^{\beta}$, where
$\gamma=\alpha/(1-\beta)$ and $0\leq\beta<1$ (See II.2). We denote by $\cal Z$
the set of isolated points. Since the complexity ${\bf C}_{0}$ is lower-
bounded by a linear function of the dimension $n$, we have

$\log n\leq a(\log N_{P})^{\alpha}+O(1).$ (57)

Let $\hat{a}_{0,1},\dots,\hat{a}_{0,n},\hat{a}_{1,1},\dots,\hat{a}_{1,n}$ be
the set of linear functions representing the matroid and satisfying Property
2. The ideal generators are given by Eq. (55).

Let $m$ be the maximum number of functions in
$\\{\hat{a}_{0,i},\dots,\hat{a}_{0,n}\\}$ which are simultaneously different
from zero for $\vec{x}\in\cal Z$. Thus, we have that

$N_{P}\leq\sum_{j=0}^{m}\frac{n!}{(n-j)!j!}\leq\left(1+n^{-1}\right){n}^{m}.$
(58)

There is a point $\vec{x}_{2}$ in $\cal Z$ such that
$\hat{a}_{0,1},\dots,\hat{a}_{0,m}$ are different from zero and
$\hat{a}_{0,m+1}=\hat{a}_{0,m+1}=\dots=\hat{a}_{0,n}=0$, up to permutations of
the indices.

Let us set these last $n-m$ functions equal to zero by dimension reduction.
The new set of generators is associated with another factoring algorithm
(Lemma 3) and contains the clauses of the form

$\begin{array}[]{l}\hat{a}_{0,i}\hat{a}_{1,i}\;\;\;i\in\\{1,\dots,m\\}\\\
\hat{a}_{0,i}\hat{a}_{0,j}\;\;\;(i,j)\in\bar{\Gamma}\subseteq\\{1,\dots,m\\}\times\\{1,\dots,m\\}.\end{array}$
(59)

Since there is a point $\vec{x}_{2}$ such that $\hat{a}_{0,i}\neq$ for
$i\in\\{1,\dots,m\\}$, the set $\bar{\Gamma}$ turns out to be empty, so that
the reduced model is diagonal. The number of common zeros of the generators,
say $N_{1}$, is equal to $2^{m}$. Using Ineq. (58), we have that

$(\log_{2}N_{1})(\log n)+\log\left(1+n^{-1}\right)\geq\log N_{P}.$ (60)

Ineq. (57) and this last inequality implies that

$\log N_{P}\leq K(\log N_{1})^{\frac{1}{1-\alpha}}$ (61)

for some constant $K$. Since the computational complexity, say $\bar{\bf
C}_{0}$ of the rational function $\cal R$ associated with the reduced model is
not greater than ${\bf C}_{0}$, which scales as $e^{a(\log N_{P})^{\alpha}}$,
we have that

$\bar{\bf C}_{0}\leq e^{\bar{a}(\log N_{1})^{\frac{\alpha}{1-\alpha}}},$ (62)

for some constant $\bar{a}$. Similarly, since the number of parameters, say
$\bar{M}$, of the reduced rational function is not greater than $M$, we have
that

$\bar{M}\leq\bar{K}(\log\bar{N}_{1})^{\frac{\beta}{1-\alpha}}$ (63)

for some constant $\bar{K}$. Thus, the resulting factoring algorithm has a
computational complexity upper-bounded by

$e^{\bar{a}(\log p)^{\frac{\alpha}{1-\alpha-\beta}}}=e^{\bar{a}(\log
p)^{\frac{\gamma}{1-\gamma}}}$

up to a constant factor. The last statement of the theorem is proved in a
similar fashion. $\square$

The diagonal model with generators

$G_{i}=\hat{a}_{0,i}\hat{a}_{1,i},\;\;\;\;\forall i\in\\{1,\dots,n\\}$ (64)

provides the simplest example of polynomials with an exponentially large
number of common zeros. The algebraic set ${\cal Z}={\cal Z}_{P}$ contains
$2^{n}$ points, which are distinct because of Property 2. This guarantees that
the generated ideal is radical. Thus, Hilbert’s Nullstellensatz implies that
every polynomial which is zero in ${\cal Z}$ can be written as
$\sum_{i}F_{i}(\vec{x})G_{i}(\vec{x})$, where $F_{1},\dots,F_{n}$ are
polynomials (let us remind that $x_{n+1}=1$).

We impose that the polynomials $P_{0},\dots,P_{n-M}$ are in the ideal
generated by $G_{1},\dots,G_{n}$, that is,

$P_{k}(\vec{x})=\sum_{i}C_{k,i}(\vec{x})\hat{a}_{0,i}\hat{a}_{1,i}\;\;\;\forall
k\in\\{0,\dots,n-M\\}.$ (65)

As there is no particular requirement on $P_{0}$, we can just set
$C_{0,i}(\vec{x})$ equal to constants. In particular, we can take
$P_{0}=\hat{a}_{0,1}\hat{a}_{1,1}$. In this case, the unknown variables of
Problem 1 are the polynomials $C_{k,i}(\vec{x})$ and the linear equations
$\hat{a}_{s,k}$ under the constraints of Property 2. In the following section
we tackle this problem with $C_{k,i}(\vec{x})$ constant.

##  V Quadratic polynomials

In this section, we illustrate the procedure described previously by
considering the special case of $n-M+1$ quadratic polynomials in the ideal $I$
generated by the polynomials (64). Namely, we take the polynomials $P_{l}$ of
the form

$P_{l}(\vec{x})=\sum_{i=1}^{n}c_{l,i}\hat{a}_{0,i}\hat{a}_{1,i},\;\;\;\;l\in\\{0,\dots,n-M\\},$
(66)

where $c_{l,i}$ are rational numbers and the linear functions $\hat{a}_{s,i}$
satisfy Property 2. Thus, there are $2^{n}$ common rational zeros of the
$n-M+1$ polynomials, which are also the zeros of the generators (64). Each
rational point is associated with a vector $\vec{s}\in\\{0,1\\}^{n}$ so that
the linear equations
$\vec{a}_{s_{1},1}\cdot\vec{x}=0,\dots,\vec{a}_{s_{n},n}\cdot\vec{x}=0$ are
satisfied.

First, we consider the case with one parameter ($M=1$). We also assume that
all the $2^{n}$ rational points are in the parametrizable variety. Starting
from these assumptions, we end up to build a variety $\cal V$ with a number
$M$ of parameters equal to $n/2-1$ for $n$ even and $n\geq 4$. Furthermore, we
prove that there is no solution with $M=1$ if $n>4$. We give a numerical
example for $n=4$, which takes to a rational function $\cal R$ with $16$
zeros. Then we build a parametrizable variety with a number of parameters
equal to $(n-1)/3$. Thus, the minimal number of parameters is some value
between $2$ and $(n-1)/3$ for the considered model with the polynomials of the
form (66).

###  V.1 One parameter? ($M=1$)

Given polynomials (66) and vectors $\vec{a}_{s,i}$ satisfying Property (2), we
search for a solution of Problem 1 under the assumption $M=1$. Let us first
introduce some notations and definitions. We define the $(n-1)\times n$
matrices

${\bf
M}^{\vec{s}}\equiv\left(\begin{array}[]{ccc}A_{1,1}^{(s_{1})}&\dots&A_{1,n}^{(s_{n})}\\\
\vdots&\ddots&\vdots\\\
A_{n-1,1}^{(s_{1})}&\dots&A_{n-1,n}^{(s_{n})}\end{array}\right),$ (67)

where

$A_{k,i}^{(s)}\equiv\frac{\partial\hat{a}_{s,i}}{\partial x_{k}},$ (68)

The square submatrix of ${\bf M}^{\vec{s}}$ obtained by deleting the $j$-th
column is denoted by ${\bf M}_{j}^{\vec{s}}$, that is,

${\bf
M}_{j}^{\vec{s}}=\left(\begin{array}[]{cccccc}A_{1,1}^{(s_{1})}&\dots&A_{1,j-1}^{(s_{j-1})}&A_{1,j+1}^{(s_{j+1})}&\dots&A_{1,n}^{(s_{n})}\\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\\
A_{n-1,1}^{(s_{1})}&\dots&A_{n-1,j-1}^{(s_{j-1})}&A_{n-1,j+1}^{(s_{j+1})}&\dots&A_{n-1,n}^{(s_{n})}\end{array}\right),$
(69)

The vectors $\vec{a}_{0,i}$ and $\vec{a}_{1,i}$ are also briefly denoted by
$\vec{a}_{i}$ and $\vec{b}_{i}$, respectively. Similarly, we also use the
symbols $A_{k,i}$ and $B_{k,i}$ for the derivatives $A_{k,i}^{(0)}$ and
$A_{k,i}^{(1)}$.

Problem 1 takes the specific form

######  Problem 2.

Find coefficients $c_{l,i}$ and vectors $\vec{a}_{s,i}$ satisfying Property
(2) such that

$\displaystyle\sum_{i=1}^{n}c_{l,i}\left(A_{k,i}\vec{a}_{i}+B_{k,i}\vec{b}_{i}\right)=0\;\;\;\;1\leq
k<l\leq n-1,\vspace{2mm}$ (70)
$\displaystyle\sum_{i=1}^{n}c_{l,i}A_{l,i}B_{l,i}=0\;\;\;\;1\leq l\leq
n-1,\vspace{2mm}$ (71) $\displaystyle\vec{x}\in{\cal
Z}_{P}\Rightarrow\sum_{i=1}^{n}c_{l,i}\left(A_{l,i}\hat{a}_{i}+B_{l,i}\hat{b}_{i}\right)\neq
0\;\;\;\;1\leq l\leq n-1.$ (72)

Let us stress again that the problem is invariant with respect to the
transformations (34,35), the latter taking to the transformation

$A_{k,i}^{(s)}\rightarrow
A_{k,i}^{(s)}+\sum_{l=1}^{k-1}\bar{\eta}_{k,l}A_{l,i}^{(s)}$ (73)

of the derivatives.

We have the following.

######  Lemma 7.

For every $\vec{s}\in\\{0,1\\}^{n}$ and $j\in\\{1,\dots,n\\}$, the matrix
${\bf M}_{j}^{\vec{s}}$ has maximal rank, that is,

$\det{\bf M}_{j}^{\vec{s}}\neq 0.$ (74)

Proof. Let us prove the lemma by contradiction. There is a
$j\in\\{1,\dots,n\\}$, $l\in\\{1,\dots,n-1\\}$, and an
$\vec{s}\in\\{0,1\\}^{n}$ such that the $l$-th row of ${\bf
M}_{j}^{{\vec{s}}}$ is linearly dependent on the first $l-1$ rows. Thus, there
are coefficients $\lambda_{1},\dots,\lambda_{l-1}$ such that

$A_{l,i}^{(s_{l})}+\sum_{k=1}^{l-1}\lambda_{k}A_{k,i}^{(s_{k})}=0\;\;\;\forall
i\neq j$ (75)

With a change of variables of the form of Eq. (35), this equation can be
rewritten in the form

$A_{l,i}^{(s_{l})}=0\;\;\;\forall i\neq j.$ (76)

Up to permutations $\hat{a}_{i}\leftrightarrow\hat{b}_{i}$, we have

$B_{l,i}=0\;\;\;\forall i\neq j.$ (77)

From Eq. (71), we have

$\sum_{i=1}^{n}c_{l,i}A_{l,i}B_{l,i}=0.$

From this equation and Eq. (77), we get the equation
$c_{l,j}A_{l,j}B_{l,j}=0$, implying that $c_{l,j}A_{l,j}=0$ or
$c_{l,j}B_{l,j}=0$. Without loss of generality, let us take

$c_{l,j}B_{l,j}=0.$ (78)

Let $\vec{x}_{0}\in{\cal Z}_{P}$ be the vector orthogonal to
$\vec{b}_{1},\dots,\vec{b}_{n}$. From Eq. (72) we have that

$c_{l,j}B_{l,j}(\vec{a}_{j}\cdot\vec{x}_{0})\neq 0,$ (79)

which is in contradiction with Ineq. (78). $\square$

######  Corollary 1.

The coefficients $c_{n-1,i}$ are different from zero for every
$i\in\\{1,\dots,n\\}$.

Proof. Let us assume that the statement is false. Up to permutations, we have
that $c_{n-1,1}=0$. Lemma 7 implies that there is an integer
$i_{0}\in\\{2,\dots,n\\}$ such that $B_{n-1,i}=0$ for $i\notin\\{1,i_{0}\\}$,
up to a transformation of the form of Eq. (35). Thus,

$0=\sum_{i=1}^{n}c_{n-1,i}A_{n-1,i}B_{n-1,i}=c_{n-1,i_{0}}A_{n-1,i_{0}}B_{n-1,i_{0}},$
(80)

the first equality coming from Eq. (71). Lemma 7 also implies that
$A_{n-1,i_{0}}B_{n-1,i_{0}}\neq 0$ Thus, on one hand, we have that
$c_{n-1,i_{0}}=0$. On the other hand, we have

$c_{n-1,i_{0}}B_{n-1,i_{0}}(\vec{a}_{i_{0}}\cdot\vec{x}_{0})\neq 0$ (81)

from Eqs. (72), where $\vec{x}_{0}$ is the vector orthogonal to
$\vec{b}_{1},\dots,\vec{b}_{n}$. Thus, we have a contradiction. $\square$

Let us denote by ${\bf M}^{\vec{s}}_{j_{1},\dots,j_{m}}$ the submatrix of
${\bf M}^{\vec{s}}$ obtained by deleting the last $m-1$ rows and the columns
$j_{1},\dots,j_{m}$. Given the coefficient matrix

${\bf c}\equiv\left(\begin{array}[]{ccc}c_{0,1}&\dots&c_{0,n}\\\
\vdots&\ddots&\vdots\\\ c_{n-1,1}&\dots&c_{n-1,n}\end{array}\right),$ (82)

let us define ${\bf c}_{j_{1},\dots,j_{m}}$ as the $m\times m$ submatrix of
${\bf c}$ obtained by keeping the last $m$ rows and the columns
$j_{1},\dots,j_{m}$.

Lemma 7 and Corollary 1 are generalized by the following.

######  Theorem 2.

For every $m\in\\{1,\dots,n-1\\}$, $\vec{s}\in\\{0,1\\}^{n}$, and $m$ distinct
integers $j_{1},\dots,j_{m}\in\\{1,\dots,n\\}$, the matrices ${\bf
M}^{\vec{s}}_{j_{1},\dots,j_{m}}$ and ${\bf c}_{j_{1},\dots,j_{m}}$ have
maximal rank, that is,

$\displaystyle\det{\bf M}^{\vec{s}}_{j_{1},\dots,j_{m}}\neq 0,$ (83)
$\displaystyle\det{\bf c}_{j_{1},\dots,j_{m}}\neq 0.$ (84)

Proof. The proof is by recursion. For $m=1$, the theorem comes from Lemma 7
and Corollary 1. Thus, we just need to prove Eqs. (83,84) by assuming that

$\displaystyle\det{\bf M}^{\vec{s}}_{j_{1},\dots,j_{m-1}}\neq 0,$ (85)
$\displaystyle\det{\bf c}_{j_{1},\dots,j_{m-1}}\neq 0.$ (86)

Let us first prove Eq. (83) by contradiction. If the equation is false, then
there is an $\vec{s}_{0}\in\\{0,1\\}^{n}$ and $m$ distinct integers
$i_{1},\dots,i_{m}$ in $\\{1,\dots,n\\}$ such that $\det{\bf
M}^{\vec{s}_{0}}_{i_{1},\dots,i_{m}}=0$. By permutations, we can set
$i_{h}=h$. By suitable exchanges of $\hat{a}_{i}$ and $\hat{b}_{i}$, we can
set $s_{i}=1$ for every $i\in\\{1,\dots,n\\}$. There is an integer
$l\in\\{1,\dots,n-m\\}$ such that $B_{l,i}=0$ for $i\in\\{m+1,\dots,n\\}$ up
to a transformation of the form of Eq. (35). From Eqs. (70,71), we have the
$m$ equations

$\begin{array}[]{r}\sum_{i=1}^{m}c_{l,i}A_{l,i}B_{l,i}=0\\\
\sum_{i=1}^{m}c_{n+1-m,i}A_{l,i}B_{l,i}=0\\\
\sum_{i=1}^{m}c_{n+2-m,i}A_{l,i}B_{l,i}=0\\\ \dots\\\
\sum_{i=1}^{m}c_{n-2,i}A_{l,i}B_{l,i}=0\\\
\sum_{i=1}^{m}c_{n-1,i}A_{l,i}B_{l,i}=0.\end{array}$ (87)

From Eq. (85), we have that $A_{l,i}\neq 0$ and $B_{l,i}\neq 0$ for some
$i\in\\{1,\dots,m\\}$, so that

$\text{rank}\left(\begin{array}[]{ccc}c_{l,1}&\dots&c_{l,m}\\\
c_{n+1-m,1}&\dots&c_{n+1-s,m}\\\ c_{n+2-m,1}&\dots&c_{n+2-s,m}\\\
\vdots&\ddots&\vdots\\\ c_{n-2,1}&\dots&c_{n-1,m}\\\
c_{n-1,1}&\dots&c_{n-1,m}\end{array}\right)<m.$ (88)

Up to a transformation of the form of Eq. (34), there is an integer
$l_{0}\in\\{n+1-m,\dots,n-1\\}\cup\\{l\\}$ such that $c_{l_{0},i}=0$ for
$i\in\\{1,\dots,m\\}$. Eq. (86) implies that $l_{0}=l$. Thus, $c_{l,1}=\dots
c_{l,m}=0$, but this contradicts Eq. (72) with $\vec{x}\in{\cal Z}_{P}$
orthogonal to $\vec{b}_{1},\dots,\vec{b}_{n}$.

Let us now prove Eq. (84) by contradiction. If the equation is false, then
there are $m$ distinct integers $i_{1},\dots,i_{m}$ in $\\{1,\dots,n\\}$ such
that $\det{\bf c}_{i_{1},\dots,i_{m}}=0$. Without loss of generality, let us
take $i_{h}=h$. Up to the transformation (34), there is an integer
$l\in\\{n-m,\dots,n-1\\}$ such that $c_{l,i}=0$ for $i\in\\{1,\dots,m\\}$. Eq.
(86) implies that $l=n-m$. Thus,

$c_{n-m,1}=\dots=c_{n-m,m}=0.$ (89)

Eq. (83) implies that there is an integer $i_{0}\in\\{m+1,\dots,n\\}$ such
that $A_{n-m,i}=0$ for $i\in\\{m+1,\dots,n\\}\char 92\relax\\{i_{0}\\}$ up to
transformation (35). Thus, we have from Eq. (71) that

$0=\sum_{i=1}^{n}c_{n-m,i}A_{n-m,i}B_{n-m,i}=c_{n-m,i_{0}}A_{n-m,i_{0}}B_{n-m,i_{0}}.$
(90)

Eq. (83) also implies that $A_{n-m,i_{0}}B_{n-m,i_{0}}\neq 0$, so that
$c_{n-m,i_{0}}=0$, which is in contradiction with Eq. (72) for $\vec{x}$
orthogonal to $\vec{a}_{1},\dots,\vec{a}_{n}$. $\square$
In the following, this theorem will be used with $m\in\\{1,2\\}$.

Since all the coefficients $c_{n-1,i}$ are different from zero, we can set
them equal to $1$ by rescaling the vectors $\vec{a}_{i}$ or $\vec{b}_{i}$. Let
us denote by $c_{i}$ the coefficients $c_{n-2,i}$. Theorem 2 with $m=2$
implies that $c_{i}\neq c_{j}$ for $i\neq j$. Eq. (70) with $l=n-1$ and
$l=n-2$ takes the form

$\displaystyle\frac{\partial}{\partial
x_{k}}P_{n-1}=\sum_{i=1}^{n}\left(A_{k,i}\vec{a}_{i}+B_{k,i}\vec{b}_{i}\right)=0\;\;\;\;1\leq
k\leq n-2,$ (91) $\displaystyle\frac{\partial}{\partial
x_{k}}P_{n-2}=\sum_{i=1}^{n}c_{i}\left(A_{k,i}\vec{a}_{i}+B_{k,i}\vec{b}_{i}\right)=0\;\;\;\;1\leq
k\leq n-3.$ (92)

These equations impose the form (32) to the last two polynomials, $P_{n-1}$
and $P_{n-2}$, which must be independent from $n-2$ and $n-3$ variables,
respectively. The first $n-2$ vector equations are linearly independent. Let
us assume the opposite. Then, there is a set of coefficients
$\lambda_{1},\dots,\lambda_{n-2}$ such that
$\sum_{k=1}^{n-2}\lambda_{k}(A_{k,i},B_{k,i})=0$. But this is impossible
because of Property 2. It also contradicts Theorem 2. The theorem also implies
that Eqs. (92) are linearly independent. Since the vector space is
$n+1$-dimensional, the vectors $\vec{a}_{i}$ and $\vec{b}_{i}$ must have $n-1$
vector constraints. Thus, at least $n-4$ out of Eqs. (92) are linearly
dependent on Eqs. (91). First, let us show that $n-4$ is the maximal number of
dependent equations. Assuming the converse, we have

$c_{i}(A_{k,i},B_{k,i})=\sum_{l=1}^{n-2}\lambda_{k,l}(A_{l,i},B_{l,i})\;\;\;\;\;\forall
k\in\\{1,\dots,n-3\\}.$ (93)

for suitable coefficients $\lambda_{k,l}$. Let us define the linear
superposition

$(A_{i},B_{i})\equiv\sum_{k=1}^{n-3}v_{k}(A_{k,i},B_{k,i})$ (94)

with the coefficients $v_{k}$. Let $\bf\Lambda$ be the $(n-2)\times(n-2)$
matrix with ${\bf\Lambda}_{k,n-2}=0$ and ${\bf\Lambda}_{k,l}=\lambda_{l,k}$
for $k\in\\{1,\dots,n-2\\}$ and $l\in\\{1,\dots,n-3\\}$. The coefficients
$(v_{1},\dots,v_{n-3})\equiv\vec{v}$ are defined by imposing the $n-4$
constraints

$({\bf\Lambda}^{s}\vec{v})_{n-2}=0\;\;\;\;\;s\in\\{1,\dots,n-4\\}.$ (95)

By construction, the pairs

$c_{i}^{k-1}(A_{i},B_{i})\;\;\;\;k\in\\{1,\dots,n-2\\}$ (96)

are linear superpositions of the derivatives $(A_{k,i},B_{k,i})$ with
$k\in\\{1,\dots,n-2\\}$. Furthermore, the first $n-3$ pairs are linear
superpositions of $(A_{k,i},B_{k,i})$ with $k\in\\{1,\dots,n-3\\}$. That is,

$\begin{array}[]{l}c_{i}^{k-1}(A_{i},B_{i})=\sum_{l=1}^{n-3}\bar{\lambda}_{k,l}(A_{l,i},B_{l,i})\;\;\;k\in\\{1,\dots,n-3\\}\\\
c_{i}^{n-3}(A_{i},B_{i})=\sum_{l=1}^{n-2}\bar{\lambda}_{n-2,l}(A_{l,i},B_{l,i})\end{array}$
(97)

for some coefficients $\bar{\lambda}_{k,l}$. From Lemma 7 and Corollary 1 we
have that the $n-2$ pairs (96) are linearly independent. Indeed, Corollary 1
implies that $A_{i}\neq 0$ and $B_{i}\neq 0$ for every $i\in\\{1,\dots,n\\}$.
Lemma 7 implies that $c_{i}^{k-1}$ are linearly independent for
$k\in\\{1,\dots,n-2\\}$. Equations (96,97) can be also derived from Jordan’s
theorem, Lemma 7 and Corollary 1. See Appendix B.

Thus, by a variable transformation, Eqs. (91,92) take the form

$\sum_{i=1}^{n}c_{i}^{k-1}\left(A_{i}\vec{a}_{i}+B_{i}\vec{b}_{i}\right)=0\;\;\;\;\;\;k\in\\{1,\dots,n-2\\}.$
(98)

and

$\frac{\partial(\hat{a}_{i},\hat{b}_{i})}{\partial
x_{k}}=c_{i}^{k-1}(A_{i},B_{i})\;\;\;\;\;\;k\in\\{1,\dots,n-2\\}.$ (99)

These equations imply that $\sum_{i=1}^{n}d_{i}^{k-1}A_{i}B_{i}=0$ for
$k\in\\{1,\dots,2n-5\\}$. For $n>4$, we have in particular that

$\sum_{i=1}^{n}c_{i}^{k-1}A_{i}B_{i}=0\;\;\;\;k\in\\{1,\dots,n\\}.$ (100)

Since

$\det\left(\begin{array}[]{ccc}1&\dots&1\\\ c_{1}&\dots&c_{n}\\\
\vdots&\ddots&\vdots\\\
c_{1}^{n-1}&\dots&c_{n}^{n-1}\end{array}\right)=\prod_{j>i}(c_{j}-c_{i})$
(101)

and $c_{i}\neq c_{j}$ for $i\neq j$, Eq. (100) implies that $A_{i}B_{i}=0$ for
every $i\in\\{1,\dots,n\\}$. But this is in contradiction with Theorem 2.

Thus, let us take exactly $n-4$ out of Eqs. (92) linearly dependent on Eqs
(91). Let $\bar{k}$ be an integer in $\\{1,\dots,n-3\\}$ such that Eq. (92)
with $k=\bar{k}$ is linearly independent of Eqs. (91). Thus,

$c_{i}(A_{k,i},B_{k,i})=\bar{\lambda}_{k}c_{i}(A_{\bar{k},i},B_{\bar{k},i})+\sum_{l=1}^{n-2}\lambda_{k,l}(A_{l,i},B_{l,i})\;\;\;\;k\in\\{1,\dots,n-3\\}\char
92\relax\\{\bar{k}\\}.$

By a transformation of the first $n-3$ variables, we can rewrite this equation
in the form.

$c_{i}(A_{k,i},B_{k,i})=\sum_{l=1}^{n-2}\lambda_{k,l}(A_{l,i},B_{l,i})\;\;\;\;k\in\\{1,\dots,n-4\\}.$
(102)

By a suitable transformation of the first $n-2$ variables, the $n-2$ pairs
$(A_{k,i},B_{k,i})$ can be split in two groups (see Appendix B), say,

$\left.\begin{array}[]{l}\frac{\partial}{\partial
x_{k}^{\prime}}(\hat{a}_{i},\hat{b}_{i})\equiv(A_{k,i}^{\prime},B_{k,i}^{\prime})=c_{i}^{k-1}(A_{i}^{\prime},B_{i}^{\prime})\;\;\;\;k\in\\{1,\dots,n_{1}\\}\\\
\frac{\partial}{\partial
x_{k}^{\prime\prime}}(\hat{a}_{i},\hat{b}_{i})\equiv(A_{k,i}^{\prime\prime},B_{k,i}^{\prime\prime})=c_{i}^{k-1}(A_{i}^{\prime\prime},B_{i}^{\prime\prime})\;\;\;\;k\in\\{1,\dots,n_{2}\\}\end{array}\right\\}\;\;\;n_{1}+n_{2}=n-2.$
(103)

Equations (91) become

$\begin{array}[]{l}\sum_{i=1}^{n}c_{i}^{k-1}\left(A_{i}^{\prime}\vec{b}_{i}+B_{i}^{\prime}\vec{a}_{i}\right)=0\;\;\;k\in\\{1,\dots,n_{1}\\}\\\
\sum_{i=1}^{n}c_{i}^{k-1}\left(\bar{A}_{i}^{\prime\prime}\vec{b}_{i}+\bar{B}_{i}^{\prime\prime}\vec{a}_{i}\right)=0\;\;\;k\in\\{1,\dots,n_{2}\\}.\end{array}$
(104)

Given these $n-2$ vector constraints, all $n-2$ the derivatives $\partial
P_{n-1}/\partial x_{1}^{\prime},\dots,\partial P_{n-1}/\partial
x_{n_{1}}^{\prime}$, $\partial P_{n-1}/\partial
x_{1}^{\prime\prime},\dots,\partial P_{n-1}/\partial x_{n_{2}}^{\prime\prime}$
are equal to zero. Furthermore, we also have that

$\begin{array}[]{l}\frac{\partial}{\partial
x_{k}^{\prime}}P_{n-2}=0\;\;\;k\in\\{1,\dots,n_{1}-1\\}\\\
\frac{\partial}{\partial
x_{k}^{\prime\prime}}P_{n-2}=0\;\;\;k\in\\{1,\dots,n_{2}-1\\},\end{array}$

so that $P_{n-2}$ is independent of $n-4$ out of the $n-2$ variables
$x_{1}^{\prime},\dots,x_{n_{1}}$,
$x_{1}^{\prime\prime},\dots,x_{n_{2}}^{\prime\prime}$. Thus, we need to add
another vector equation such that $\left(w_{1}\frac{\partial}{\partial
x_{n_{1}}^{\prime}}+w_{2}\frac{\partial}{\partial
x_{n_{2}}^{\prime\prime}}\right)P_{n-2}=0$ for some $(w_{1},w_{2})\neq(0,0)$.
Up to a variable transformation, we can set $(w_{1},w_{2})=(1,0)$ so that the
additional vector equation is

$\sum_{i=1}^{n}c_{i}^{n_{1}}\left(A_{i}^{\prime}\vec{b}_{i}+B_{i}^{\prime}\vec{a}_{i}\right)=0.$
(105)

Equations (71,104,105) imply that

$\displaystyle\sum_{i=1}^{n}c_{i}^{k-1}A_{i}^{\prime}B_{i}^{\prime}=0\;\;\;k\in\\{1,\dots,2n_{1}\\},$
(106)
$\displaystyle\sum_{i=1}^{n}c_{i}^{k-1}A_{i}^{\prime\prime}B_{i}^{\prime\prime}=0\;\;\;k\in\\{1,\dots,2n_{2}\\},$
(107)
$\displaystyle\sum_{i=1}^{n}c_{i}^{k-1}(A_{i}^{\prime}B_{i}^{\prime\prime}+A_{i}^{\prime\prime}B_{i}^{\prime})=0\;\;\;k\in\\{1,\dots,n_{1}+n_{2}\\}.$
(108)

Since $A_{i}^{\prime}B_{i}^{\prime}$ and $A_{i}^{\prime}B_{i}^{\prime}$ are
not identically equal to zero (as consequence of Theorem 2), the number of
Eqs. (106) and Eqs. (107) is smaller than $n$, so that

$n_{1}\leq\frac{n-1}{2},\;\;\;n_{2}\leq\frac{n-1}{2}.$

Without loss of generality, we can assume that $n$ is even. Indeed, if Problem
1 can be solved for $n$ odd, then Lemma 3 implies that it can be solve for $n$
even, and viceversa. Since $n_{1}+n_{2}=n-2$, we have that

$n_{1}=n_{2}=\frac{n-2}{2}.$ (109)

Let $W_{1},\dots,W_{n}$ be $n$ numbers defined by the equations

$\sum_{i=1}^{n}c_{i}^{k-1}W_{i}=0\;\;\;\;k\in\\{1,\dots,n-1\\}$ (110)

up to a constant factor. Equations (106,107,108) are equivalent to the
equations

$\displaystyle A_{i}^{\prime}B_{i}^{\prime}=(k_{0}+k_{1}c_{i})W_{i},$ (111)
$\displaystyle
A_{i}^{\prime\prime}B_{i}^{\prime\prime}=(r_{0}+r_{1}c_{i})W_{i},$ (112)
$\displaystyle
A_{i}^{\prime}B_{i}^{\prime\prime}+A_{i}^{\prime\prime}B_{i}^{\prime}=(s_{0}+s_{1}c_{i})W_{i}.$
(113)

These equations can be solved over the rationals for the coefficients $c_{i}$,
$B_{i}^{\prime}$ and $B_{i}^{\prime\prime}$ in terms of $A_{i}^{\prime}$ and
$A_{i}^{\prime\prime}$. The coefficients $c_{i}$ take a form which is
independent of $W_{i}$,

$c_{i}=\frac{r_{0}A_{i}^{\prime\,2}+k_{0}A_{i}^{\prime\prime\,2}-s_{0}A_{i}^{\prime}A_{i}^{\prime\prime}}{r_{1}A_{i}^{\prime\,2}+k_{1}A_{i}^{\prime\prime\,2}-s_{1}A_{i}^{\prime}A_{i}^{\prime\prime}},$
(114)

so that we first evaluate $c_{i}$, then $W_{i}$ by Eq. (110) and, finally,
$B_{i}^{\prime}$ and $B_{i}^{\prime\prime}$ by Eqs. (111,112). It is possible
to show that condition (72) for $l=n-1$ implies that $(k_{1},r_{1})\neq(0,0)$.
Indeed, if $(k_{1},r_{1})=(0,0)$, then only half of the points in ${\cal
Z}_{P}$ satisfies the inequality in the condition. Up to a variable change, we
have

$k_{1}\neq 0,\;\;\;s_{1}=0.$

Up to now we have been able to solve all the conditions of Problem 2 which
refer to the last two polynomials, that is, for $l=n-2,n-1$. The equations
that need to be satisfied are Eqs. (104,105, 110,111,112,113). Let us rewrite
them all together.

$\boxed{\begin{array}[]{c}A_{i}^{\prime}B_{i}^{\prime}=(k_{0}+k_{1}c_{i})W_{i},\;\;\;A_{i}^{\prime\prime}B_{i}^{\prime\prime}=(r_{0}+r_{1}c_{i})W_{i}\\\
A_{i}^{\prime}B_{i}^{\prime\prime}+A_{i}^{\prime\prime}B_{i}^{\prime}=s_{0}W_{i},\;\;\;k_{1}\neq
0\vspace{1mm}\\\
\sum_{i=1}^{n}c_{i}^{k-1}W_{i}=0\;\;\;\;k\in\\{1,\dots,n-1\\}\vspace{1mm}\\\
\sum_{i=1}^{n}c_{i}^{k-1}\left(A_{i}^{\prime}\vec{b}_{i}+B_{i}^{\prime}\vec{a}_{i}\right)=0\;\;\;k\in\\{1,\dots,\frac{n}{2}\\}\\\
\sum_{i=1}^{n}c_{i}^{k-1}\left(\bar{A}_{i}^{\prime\prime}\vec{b}_{i}+\bar{B}_{i}^{\prime\prime}\vec{a}_{i}\right)=0\;\;\;k\in\\{1,\dots,\frac{n}{2}-1\\}\end{array}}$
(115)

Given $2n$ vectors
$\vec{a}_{1},\dots,\vec{a}_{n},\vec{b}_{1},\dots,\vec{b}_{n}$ satisfying these
equations, there are $n-1$ directions $\vec{u}_{1},\dots,\vec{u}_{n-1}$ such
that

$\begin{array}[]{l}\vec{u}_{2k-1}\cdot\frac{\partial}{\partial\vec{x}}(\hat{a}_{i},\hat{b}_{i})=c_{i}^{k-1}(A_{i}^{\prime},B_{i}^{\prime})\;\;\;k\in\\{1,\dots,\frac{n}{2}-1\\}\\\
\vec{u}_{2k}\cdot\frac{\partial}{\partial\vec{x}}(\hat{a}_{i},\hat{b}_{i})=c_{i}^{k-1}(A_{i}^{\prime\prime},B_{i}^{\prime\prime})\;\;\;k\in\\{1,\dots,\frac{n}{2}\\}.\end{array}$
(116)

This can be easily verified by substitution. Let us define the coordinate
system $(y_{1},\dots,y_{n+1})\equiv\vec{y}$ such that

$\vec{u}_{k}\cdot\frac{\partial}{\partial\vec{x}}=\frac{\partial}{\partial
y_{k}}\;\;\;k\in\\{1,\dots,n-1\\}.$ (117)

Given the polynomials

$\begin{array}[]{l}P_{n-1}=\sum_{i=1}^{n}\hat{a}_{i}\hat{b}_{i}\\\
P_{n-2}=\sum_{i=1}^{n}c_{i}\hat{a}_{i}\hat{b}_{i}\end{array}$ (118)

with $\hat{a}_{i}=\vec{a}_{i}\cdot\vec{y}$ and
$\hat{b}_{i}=\vec{b}_{i}\cdot\vec{y}$, it is easy to verify that

$\begin{array}[]{l}\frac{\partial P_{n-1}}{\partial
y_{k}}=0,\;\;\;\;k\in\\{1,\dots,n-2\\},\\\ \frac{\partial P_{n-2}}{\partial
y_{k}}=0,\;\;\;\;k\in\\{1,\dots,n-3\\},\\\ \frac{\partial^{2}P_{n-2}}{\partial
y_{n-2}^{2}}=0.\end{array}$ (119)

The polynomial $P_{n-1}$ depends on $2$ variables (in the affine space) and
the polynomial $P_{n-2}$ depends linearly on an additional variable $y_{n-2}$.
Thus, the algebraic set of the two polynomials admits a Gaussian
parametrization, that is, the equations $P_{n-1}=0$ and $P_{n-2}=0$ can be
solved with _a la_ Gauss elimination of two variables. Note that the
polynomial $P_{n-1}$ has rational roots by construction. The next step is to
satisfy the conditions of Problem 2 for the other polynomials
$P_{1},\dots,P_{n-3}$ by setting $c_{k,i}$ and the other remaining free
coefficients. It is interesting to note that it is sufficient to take
$c_{2s,i}=c_{i}^{n/2-s}$ with $s\in\\{1,\dots,(n-4)/2\\}$ for satisfying every
condition of Problem 2 for $l$ even. The polynomials
$P_{2},P_{4},\dots,P_{n-2}$ take the form

$P_{2s}=\sum_{i=1}^{n}c_{i}^{n/2-s}\hat{a}_{i}\hat{b}_{i},\;\;\;s\in\\{1,\dots,(n-4)/2\\}.$
(120)

Furthermore, we can choose $c_{1,i}$ such that $\partial^{2}P_{1}/\partial
x_{1}^{2}=0$. With this choice, we have that

$\left.\begin{array}[]{l}\frac{\partial P_{l}}{\partial
y_{k}}=0,\;\;\;\;k\in\\{1,\dots,l-1\\}\\\ \frac{\partial^{2}P_{l}}{\partial
y_{l}^{2}}=0\end{array}\right\\}\;\;\;l\in\\{2,4,\dots,n-4,n-2\\}\cup\\{1,n-1\\}.$
(121)

Thus, we are halfway to solve Problem 2, about half of the conditions are
satisfied. The hard core of the problem is to solve the conditions for
$P_{1},P_{3},\dots,P_{n-3}$. The form of Polynomials (120) is not necessarily
the most general. Thus, let us take a step backward and handle Problem 2 for
the polynomial $P_{n-3}$ with the equations derived so far. We will find that
this polynomial cannot satisfy the required conditions if $n>4$, so that the
number of parameters has to be greater than $1$.

Let us denote by $d_{i}$ the coefficients $c_{n-3,i}$. Eqs. (70,71) with
$l=n-3$ give the equations

$\sum_{i=1}^{n}e_{i}\left(A_{k,i}B_{k^{\prime},i}+A_{k^{\prime},i}B_{k,i}\right)=0\;\;\;k,k^{\prime}\in\\{1,\dots,n-3\\},$

which imply that

$\begin{array}[]{l}\sum_{i=1}^{n}e_{i}c_{i}^{k+k^{\prime}-2}A_{i}^{\prime}B_{i}^{\prime}=0\;\;\;k,l\in\\{1,\dots,\frac{n}{2}-1\\}\\\
\sum_{i=1}^{n}e_{i}c_{i}^{k+k^{\prime}-2}A_{i}^{\prime\prime}B_{i}^{\prime\prime}=0\;\;\;k,l\in\\{1,\dots,\frac{n}{2}-2\\}\\\
\sum_{i=1}^{n}e_{i}c_{i}^{k+k^{\prime}-2}\left(A_{i}^{\prime}B_{i}^{\prime\prime}+A_{i}^{\prime\prime}B_{i}^{\prime}\right)=0\;\;\;\left\\{\begin{array}[]{l}k\in\\{1,\dots,\frac{n}{2}-1\\}\\\
k^{\prime}\in\\{1,\dots,\frac{n}{2}-2\\}\end{array}\right.\end{array}$

that is,

$\begin{array}[]{l}\sum_{i=1}^{n}e_{i}c_{i}^{k-1}A_{i}^{\prime}B_{i}^{\prime}=0\;\;\;k\in\\{1,\dots,n-3\\}\\\
\sum_{i=1}^{n}e_{i}c_{i}^{k-1}A_{i}^{\prime\prime}B_{i}^{\prime\prime}=0\;\;\;k\in\\{1,\dots,n-5\\}\\\
\sum_{i=1}^{n}e_{i}c_{i}^{k-1}\left(A_{i}^{\prime}B_{i}^{\prime\prime}+A_{i}^{\prime\prime}B_{i}^{\prime}\right)=0\;\;\;k\in\\{1,\dots,n-4\\}.\end{array}$
(122)

These equations imply that

$\begin{array}[]{l}e_{i}A_{i}^{\prime}B_{i}^{\prime}=F_{11}(c_{i})W_{i}\\\
e_{i}A_{i}^{\prime\prime}B_{i}^{\prime\prime}=F_{22}(c_{i})W_{i}\\\
e_{i}\left(A_{i}^{\prime}B_{i}^{\prime\prime}+A_{i}^{\prime\prime}B_{i}^{\prime}\right)=F_{12}(c_{i})W_{i},\end{array}.$
(123)

where $F_{11}(x)$, $F_{22}(x)$ and $F_{12}(x)$ are polynomials of degree lower
than $3$, $5$ and $4$, respectively. Thus,

$e_{i}=\frac{F_{11}(c_{i})}{k_{0}+k_{1}c_{i}}=\frac{F_{22}(c_{i})}{r_{0}+r_{1}c_{i}}=\frac{F_{12}(c_{i})}{s_{0}}.$
(124)

The second and third equalities give polynomials of degree lower than $6$ and
$5$, respectively. Since $c_{i}\neq c_{j}$ for $i\neq j$ and $n$ is even, the
coefficients of these polynomials are equal to zero for $n>4$. In particular,
$k_{0}+k_{1}c_{i}$ divides $F_{11}(c_{i})$ and, thus, $e_{i}$ is equal to a
linear function of $c_{i}$. We have that $P_{n-3}=q_{1}P_{n-2}+q_{2}P_{n-1}$
for some constants $q_{1}$ and $q_{2}$, so that there is no independent
polynomial $P_{n-3}$ satisfying the required conditions for $n>4$. In
conclusion, we searched for a solution of Problem 2 with one parameter
($M=1$), but we ended up to find a solution with $n/2-1$ parameters. Let us
stress that we have not proved that $M$ cannot be less than $n/2-1$, we have
only proved that $P_{n-3}$ cannot satisfy the required conditions, so that
solutions with $M>1$ may exist. Furthermore, we employed the condition $M=1$
in some intermediate inferences. Thus, to check the existence of better
solutions, we need to consider the case $M\neq 1$ from scratch.

For the sake of completeness, let us write down the solution for $n=4$. Eqs.
(122) reduce to

$\sum_{i=1}^{n}e_{i}A_{i}^{\prime}B_{i}^{\prime}=0,$ (125)

Up to a replacement
$P_{1}\rightarrow\lambda_{1}P_{1}+\lambda_{2}P_{2}+\lambda_{3}P_{3}$ for some
constants $\lambda_{i}$ with $\lambda_{1}\neq 0$, we have that

$e_{i}=\frac{1}{k_{0}+k_{1}c_{i}}.$ (126)

Thus, the $4$ polynomials take the form

$\begin{array}[]{ll}P_{0}=\hat{a}_{1}\hat{b}_{1},&P_{1}=\sum_{i=1}^{4}\frac{\hat{a}_{i}\hat{b}_{i}}{k_{0}+k_{1}c_{i}}\\\