P_{2}=\sum_{i=1}^{4}c_{i}\hat{a}_{i}\hat{b}_{i}&P_{3}=\sum_{i=1}^{4}\hat{a}_{i}\hat{b}_{i}.\end{array}$
(127)

Let us give a numerical example with $4$ polynomial, built by using the
derived equations.

####  V.1.1 Numerical example with $n=$4

Let us set $A_{i}^{\prime}=i$, $A_{i}^{\prime\prime}=1$,
$k_{0}=k_{1}=r_{0}=1$, $r_{1}=2$, and $s_{0}=3$. Up to a linear transformation
of $x_{3}$ and $x_{4}$, this setting gives the polynomials

$\begin{array}[]{l}P_{3}(x_{3},x_{4})=\\\
5x_{3}\left(8427x_{4}+9430\right)-209\left(3x_{4}\left(393x_{4}+880\right)+1478\right)\vspace{1mm}\\\
P_{2}(x_{2},x_{3},x_{4})=\\\
5538425x_{3}^{2}+18810\left(1445x_{2}+5718x_{4}+6421\right)x_{3}-786258\left(3x_{4}\left(267x_{4}+598\right)+1004\right)\vspace{1mm}\\\
P_{1}(x_{1},x_{2},x_{3},x_{4})=\\\
2299[205346285x_{3}-38(63526809x_{4}+35594957)]-5[-2045057058x_{2}^{2}+\\\
1630827(1813x_{3}+1254x_{4})x_{2}+2891872832x_{3}^{2}+495958966272x_{4}^{2}+\\\
4892481x_{1}(1254x_{2}-1429x_{3}-418)-87093628743x_{3}x_{4}]\vspace{1mm}\\\
P_{0}(x_{1},x_{2},x_{3},x_{4})=\\\
\left(627x_{1}+627x_{2}-46x_{3}+1881\left(x_{4}+1\right)\right)\left(5016x_{1}+6270x_{2}+2555x_{3}-3762\left(4x_{4}+5\right)\right)\end{array}$
(128)

Taking $x_{4}$ as the parameter $\tau$ and solving the equations
$P_{3}=P_{2}=P_{1}=0$ with respect to $x_{3}$, $x_{2}$ and $x_{1}$, we replace
the result in $P_{0}$ and obtain, up to a constant factor,

${\cal
R}(\tau)=\frac{\prod_{k=1}^{16}(\tau-\tau_{k})}{Q_{1}^{2}(\tau)Q_{2}^{2}Q_{3}^{2}(\tau)},$
(129)

where

$\begin{array}[]{l}Q_{1}(\tau)=8427\tau+9430,\\\
Q_{2}(\tau)=3\tau(393\tau+880)+1478,\\\
Q_{3}(\tau)=3\tau(9\tau(7\tau(5367293625\tau+24273841402)+288165964484)+1954792734568)+1657527934720,\\\
(\tau_{1},\dots\tau_{16})=-\left(\frac{86}{69},\frac{800}{681},\frac{122}{105},\frac{3166}{2775},\frac{140}{123},\frac{718}{633},\frac{2452}{2163},\frac{5558}{4929},\frac{2578}{2289},\frac{152}{135},\frac{1070}{951},\frac{3932}{3507},\frac{158}{141},\frac{2072}{1851},\frac{1142}{1023},\frac{218}{201}\right)\end{array}$
(130)

Over a finite field $\mathbb{Z}_{p}$, one can check that the numerator has
about $16$ distinct roots for $p\gg 16$. For $p\simeq 16$, the roots are lower
because of collision or because the denominator of some rational root
$\tau_{k}$ is divided by $p$.

####  V.1.2 Brief excursus on retro-causality and time loops

Previously, we have built the polynomials (120). Setting them equal to zero,
we have a triangular system of about $n/2$ polynomial equations that can be
efficiently solved in $n/2$ variables, say ${\bf x}_{1}$, given the value of
the other variables, say ${\bf x}_{2}$. This system is more or less symmetric,
that is, the variables ${\bf x}_{2}$ can be efficiently computed given the
first block ${\bf x}_{1}$ (up to few variables). To determine the overall set
of variables, we need the missing $n/2$ polynomials in the ideal $I$. It is
possible to choose the coefficients $c_{l,i}$ of these polynomials in a such a
way that the associated equations have again a triangular form with respect to
one of the two blocks ${\bf x}_{1}$ and ${\bf x}_{2}$, up to few variables.
Thus, we end up with two independent equations and a boundary condition,

$\begin{array}[]{l}{\bf x}_{2}={\cal R}_{1}({\bf x}_{1}),\\\ {\bf x}_{3}={\cal
R}_{2}({\bf x}_{2}),\\\ {\bf x}_{3}={\bf x}_{1},\end{array}$ (131)

where ${\cal R}_{1}$ and ${\cal R}_{2}$ vectorial rational functions. The
first two equations can be interpreted as time-forward and time-backward
processes. The last equation identifies the initial state of the forward
process with the final state of the backward process. The overall process can
be seen also as a deterministic process in a time loop. This analogy is
suggestive, since retro-causality is considered one possible explanation of
quantum weirdness. Can a suitable break of causality allow for a description
of quantum processes in a classical framework? To be physically interesting,
this break should not lead to a computational power beyond the power of
quantum computers, otherwise a fine tuning of the theory would be necessary to
conceal, in a physical process, much of the power allowed by the causality
break. A similar fine tuning is necessary if, for example, quantum non-
locality is explained with superluminar interactions. These classical non-
local theories need an artificial fine tuning to account for non-signaling of
quantum theory.

###  V.2 $(n-1)/3$ parameters at most

In the previous subsection, we have built a class of curves defined by systems
of $n-1$ polynomial equations such that about half of the variables can be
efficiently solved over a finite field as functions of the remaining
variables. These curves and the polynomial $P_{0}$ have $2^{n}$ rational
intersection points. From a different perspective (discarding about $n/2$
polynomials), we have found a parametrizable variety with about $n/2$
parameters such that its intersection with some hypersurface has $2^{n}$
rational points.

In this subsection, we show that the number of parameters can be dropped to
about $n/3$ so that about $2n/3$ variables can be efficiently eliminated, at
least. In the following, we consider space dimensions $n$ such that $n-1$ is a
multiple of $3$. Let us define the integer

$n_{1}\equiv\frac{n-1}{3}.$ (132)

Let us define the rational numbers $A_{i},B_{i},\bar{A}_{i},\bar{B}_{i}$,
$W_{i}$, and $c_{i}$ with $i\in\\{1,\dots,n\\}$ as a solution of the equations

$\begin{array}[]{c}A_{i}B_{i}=W_{i},\;\;\;\bar{A}_{i}\bar{B}_{i}=W_{i},\\\
A_{i}\bar{B}_{i}+\bar{A}_{i}B_{i}=2c_{i}W_{i},\\\
\sum_{i=1}^{n}c_{i}^{k-1}W_{i}=0\;\;\;\;k\in\\{1,\dots,n-1\\},\\\ i\neq
j\Rightarrow c_{i}\neq c_{j}.\end{array}$ (133)

The procedure for finding a solution has been given previously. We define the
polynomials

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

The linear functions $\hat{a}_{i}$ and $\hat{b}_{i}$ are defined by the $n-1$
linear equations

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

These equations uniquely determine $\hat{a}_{i}$ and $\hat{b}_{i}$, up to a
linear transformation of the variables $x_{i},\dots,x_{n+1}$. Up to a linear
transformation, we have

$\begin{array}[]{l}\frac{\partial(\hat{a}_{i},\hat{b}_{i})}{\partial
x_{k}}=c_{i}^{k-1}(\bar{A}_{i},\bar{B}_{i}),\;\;\;k\in\\{1,\dots,n_{1}\\}\\\
\frac{\partial(\hat{a}_{i},\hat{b}_{i})}{\partial
x_{k+n_{1}}}=c_{i}^{k-1}(A_{i},B_{i}),\;\;\;k\in\\{1,\dots,n_{1}\\}.\end{array}$
(136)

Since there are rational points in the curve, there is another variable, say
$x_{2n_{1}+1}$, such that the second derivative $\partial^{2}P_{1}/\partial
x_{2n_{1}+1}^{2}$ is equal to zero. Using the above equations, we have

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

Thus, the first $2n_{1}+1=\frac{2n+1}{3}$ polynomials take the triangular form
(32), up to a reorder of the indices. These polynomials define a
parametrizable variety with $(n-1)/3$ parameters. Stated in a different way,
there is a curve and a hypersurface such that their intersection contains
$2^{n}$ points and at least $(2n+1)/3$ coordinates of the points in the curve
can be evaluated efficiently given the value of the other coordinates. It is
possible to show that all the intersection points are in the parametrizable
variety, that is, they satisfy the third of Conditions (50).

##  VI Conclusion and perspectives

In this paper, we have reduced prime factorization to the search of rational
points of a parametrizable variety $\cal V$ having an arbitrarily large number
$N_{P}$ of rational points in the intersection with a hypersurface $\cal H$.
To reach a subexponential factoring complexity, the number of parameters $M$
has to grow sublinearly in the space dimension $n$. In particular, If $N_{P}$
grows exponentially in $n$ and $M$ scales as a sublinear power of $n$, then
the factoring complexity is polynomial (subexponential) if the computation of
a rational point in $\cal V$, given the parameters, requires a number of
arithmetic operations growing polynomially (subexponentially) in the space
dimension. Here, we have considered a particular kind of rational
parametrization. A set of $M$ coordinates, say $x_{n-M+1},\dots,x_{n}$, of the
points in $\cal V$ are identified with the $M$ parameters, so that the first
$n-M$ coordinates are taken equal to rational functions of the last $M$
coordinates. In particular, the parametrization is expressed in a triangular
form. The $k$-th variable is taken equal to a rational function ${\cal
R}_{k}={\cal N}_{k}/{\cal D}_{k}$ of the variables $x_{k+1},\dots,x_{n}$, with
$k\in\\{1,\dots,n-M\\}$. That is,

$\begin{array}[]{l}x_{k}={\cal
R}_{k}(x_{k+1},\dots,x_{n}),\;\;\;k\in\\{1,\dots,n-M\\},\end{array}$ (138)

which parametrize a variety in the zero locus of the $n-M$ polynomials,

$P_{k}={\cal D}_{k}x_{k}-{\cal N}_{k},\;\;\;\;k\in\\{1,\dots,n-M\\}.$ (139)

To reach polynomial complexity, there are two requirements on these
polynomials. First, they have to contain a number of monomials scaling
polynomially in $n$, so that the computation of ${\cal R}_{k}$ is efficient.
For example, we could require that the degree is upper-bounded by some
constant. Second, their zero locus has to share an exponentially large number
of rational points with some hypersurface $\cal H$ (a superpolynomial scaling
$N_{P}\sim e^{b\,n^{\beta}}$ with $0<\beta<1$ is actually sufficient, provided
that the growth of $M$ is sufficiently slow). The hypersurface is the zero
locus of some polynomial $P_{0}$. Also the computation of $P_{0}$ at a point
has to be efficient.

We have proposed a procedure for building pairs $\\{{\cal V},{\cal H}\\}$
satisfying the two requirements. First, we define the set of $N_{P}$ rational
points. This set can depend on some coefficients. Since $N_{P}$ has to grow
exponentially in the dimension, we need to define them implicitly as common
zeros of a set of polynomials, say $G_{1},G_{2},\dots$. The simplest way is to
take $G_{k}$ as products of linear functions, like the polynomials (3). These
polynomials generate an ideal $I$. The relevant information on the generators
is encoded in a satisfiability formula in conjunctive normal form without
negations and a linear matroid. We have called these two objects a model.
Second, we search for $n-M$ polynomials in $I$ with the triangular form (139).
These polynomials always exist. Thus, the task is to find a solution such that
the polynomials contain as few monomials as possible. This procedure is
illustrated with the simplest example. The generators are taken equal to
reducible quadratic polynomials of the form (3), whose associated algebraic
set contains $2^{n}$ rational points. We search for polynomials $P_{k}$ of the
form $\sum_{i}c_{i}G_{i}$ with $c_{i}$ constant. First, we prove that there is
no solution for $M=1$ and space dimension greater than $4$. Then, we find a
solution for $M=(n-1)/3$. If there are solutions with $M$ scaling sublinearly
in $n$, then a factoring algorithm with polynomial complexity automatically
exists, since the computational complexity of the rational functions ${\cal
R}_{k}$ is polynomial by construction. The existence of such solutions is left
as an open problem.

This work can proceed in different directions. First, it is necessary to
investigate whether the studied model admits solutions with a much smaller set
of parameters. The search has been performed in a subset of the ideal. Thus,
if these solutions do not exist, we can possibly expand this subset (if it is
sufficiently large, there is for sure a solution, but the polynomial
complexity of ${\cal R}_{k}$ is not guaranteed anymore). We could also relax
other hypotheses such as the distinguishibility of each of the $2^{n}$
rational points and their membership of the parametrizable variety. More
general ideals are another option. In this context, we have shown that classes
of models can be reduced to smaller classes by preserving the computational
complexity of the associated factoring algorithms. This reduction makes the
search space smaller. It is interesting to determine what is the minimal class
of models obtained by this reduction. This is another problem left open. Apart
from the search of better inputs of the procedure, there is a generalization
of the procedure itself. The variety $\cal V$ has the parametrization (138).
However, there are more general parametrizable varieties which can be taken in
consideration. It is also interesting to investigate if there is some deeper
relation with retro-causality, time loops and, possibly, a connection with
Shor algorithm. Indeed, in the attempt of lowering the geometric genus of one
of the non-parametrizable curves derived in the previous section, we found a
set of solutions for the coefficients over the cyclotomic number field, so
that the resulting polynomials have terms taking the form of a Fourier
transform. Quantum Fourier transform is a key tool in Shor’s algorithm. This
solution ends up to break the curve into the union of an exponential large
number of parametrizable curves, thus it is not useful for our purpose.
Nonetheless, the Fourier-like forms in the polynomials remains suggestive.
Finally, the overall framework has some interesting relation with the
satisfiability problem. Using a particular matroid, we have seen that there is
a one-to-one correspondence between the points of an algebraic set and the
solutions of a satisfiability formula (including also negations). To prove
that a formula is satisfiable is equivalent to prove that a certain algebraic
set is not empty. This mapping of SAT problems to an algebraic-geometry
problem turns out to be a generalization of previous works using the finite
field $\mathbb{Z}_{2}$, see for example Ref. hung . It can be interesting to
investigate whether part of the machinery introduced here can be used for
solving efficiently some classes of SAT formulae.

##  VII Acknowledgments

This work was supported by Swiss National Science Foundation (SNF) and Hasler
foundation under the project n. 16057.

##  Appendix A Basics of algebraic geometry

###  A.1 Ideals in polynomial rings and algebraic sets

Given a field $K$, a _polynomial ring_ $K[X_{1},\dots,X_{n}]$ is a ring whose
elements are polynomials in $n$ variables. An _ideal_ $I$ in the polynomial
ring is a subset of the ring closed with respect to the addition of elements
in $I$ and the multiplication of elements in $I$ by elements of the ring.
Every ideal $I$ in the polynomial ring is generated by a finite set of
polynomials in $I$ (Hilbert’s basis theorem). Given a set of generators
$G_{1},\dots,G_{m}$ of $I$, every element of the ideal can be written in the
form $\sum_{k=1}^{m}F_{k}G_{k}$, where $F_{k}$ are polynomials in the ring. An
ideal has infinite possible sets of generators. A set of generators is a
particular representation of the ideal and a change of generators is similar
to a change of basis in a vector space. There is a correspondence between
ideals and algebraic sets. _Algebraic sets_ are subsets of an affine space
whose elements are all the common zeros of some set of polynomials in the
algebraically closed extension $\bar{K}$ of $K$. This set of polynomials
generates an ideal. By definition of ideals, the common zeros of a set of
polynomials are common zeros of every polynomial in the generated ideal. Thus,
we can associate ideals with algebraic sets. This takes to the following
equivalent definition of algebraic set.

######  Definition 6.

A subset $V$ of an affine space is an algebraic set if there is an ideal $I$
such that the common zeros of the polynomials in $I$ are all the elements in
$S$. An algebraic set associated with an ideal $I$ is denoted by ${\bf V}(I)$.

This definition of algebraic set is more appealing as it does not refer to a
particular representation of the ideal. The correspondence between ideals and
algebraic sets is not one-to-one and an algebraic set is associated with many
different ideals. For example, let ${\bf V}(I)$ be the algebraic set of the
ideal $I$ with generators $G_{1},\dots,G_{m}$. Let $J$ be the ideal generated
by $G_{1}^{k},G_{2},\dots,G_{m}$, where $k$ is some integer greater than $1$.
In general, the ideal $J$ is a strict subset of $I$. It is easy to find
examples for which $J\subset I$, such as $G_{i}=x_{i}$ with
$i\in\\{1,\dots,n\\}$ and $m=n$. The common zeros of the polynomials in $J$
are all the elements in ${\bf V}(I)$. Thus ${\bf V}(I)={\bf V}(J)$, but
$J\subset I$. A stricter correspondence between ideals and algebraic sets is
obtained by associating an algebraic set $V$ with the largest ideal $I$ such
that $V={\bf V}(I)$, called the _vanishing ideal_.

######  Definition 7.

Given an algebraic set $V$, we define the vanishing ideal of $V$ as

${\bf I}(V)\equiv\bigcup_{{\bf V}(I)=V}I.$ (140)

In other words, ${\bf I}(V)$ is the set of all the polynomials which are zero
in $V$.

The composition ${\bf I}({\bf V}(I))\equiv I^{*}$ maps an ideal $I$ to the
largest ideal with same associated algebraic set. This map is idempotent, that
is, $(I^{*})^{*}=I^{*}$. We have

${\bf I}({\bf V}(I))={\bf I}({\bf V}(I^{*}))=I^{*}.$

Thus, there is bijective correspondence between algebraic sets and ideals of
the form $I^{*}$.

Hilbert’s Nullstellensatz identifies the operation $I^{*}$ with the
radicalization of $I$.

######  Definition 8.

The _radical_ of an ideal $I$, denoted by $\sqrt{I}$, is an ideal satisfying
the double implication

$a\in\sqrt{I}\Leftrightarrow\exists k\mathbb{\in}{Z}^{+}\text{ s.t. }a^{k}\in
I.$

The radical of an ideal $I$ contains $I$. If $\sqrt{I}=I$, $I$ is called
_radical ideal_ or _semiprime ideal_.

Also the radicalization of an ideal is an idempotent operation, that is,
$\sqrt{\sqrt{I}}=\sqrt{I}$. Since the polynomials $a$ and $a^{k}$ share the
same zeros, it comes that

${\bf V}(I)={\bf V}(\sqrt{I}).$

######  Theorem 3.

(Hilbert’s Nullstellensatz) Given the algebraic set $V\equiv{\bf V}(I)$ of an
ideal $I$, a polynomial is zero in $V$ if and only if it is an element of
$\sqrt{I}$, that is, $\sqrt{I}=I^{*}$.

Thus,

${\bf I}({\bf V}(I))={\bf I}({\bf V}(\sqrt{I}))=\sqrt{I}.$

######  Definition 9.

The _intersection_ of $I\cap J$ of two ideals $I$ and $J$ is an ideal whose
elements are both in $I$ and $J$.

It comes from the definition of intersection that

${\bf V}(I\cap J)={\bf V}(I)\cup{\bf V}(J).$ (141)

######  Definition 10.

A _prime ideal_ $p$ of a polynomial ring $K[X_{1},\dots,X_{n}]$ is a strict
subset of the ring such that, for every $a$ and $b$ in the ring, $ab\in p$
implies that $a$ or $b$ are in $p$.

A prime ideal generalizes the concept of prime integers. The ideal generated
by a prime integer in the ring $\mathbb{Z}$ is a prime ideal. Excluding the
ring among the prime ideals is like excluding $1$ among prime numbers, whose
ideal is the whole ring $\mathbb{Z}$.

######  Lemma 8.

The radical of an ideal $I$ is equal to the intersection of every prime ideal
containing $I$, that is,

$\sqrt{I}=\bigcap_{p\text{ prime},\;p\supseteq I}p$ (142)

Let us illustrate this lemma with an example in one dimension. Let $I$ be the
ideal generated by the polynomial
$P=(x_{1}-k_{1}x_{0})^{a_{1}}\dots(x_{1}-k_{m}x_{0})^{a_{m}}$, where the
exponents are positive integers and $i\neq j\Rightarrow k_{i}\neq k_{j}$. Its
radical is generated by $P_{r}=(x_{1}-k_{1}x_{0})\dots(x_{1}-k_{m}x_{0})$.
There are $m$ prime ideals containing $I$ and they are generated by the linear
polynomials $(x_{1}-k_{1}x_{0}),(x_{1}-k_{2}x_{0}),\dots,(x_{1}-k_{m}x_{0})$.
Their intersection is the ideal generated by $P_{r}$, in accordance with the
lemma.

A direct consequence of Lemma 8 is the following.

######  Corollary 2.

If $I$ and $J$ are radicals, then also $I\cap J$ is radical.

This lemma and Eq. (141) imply that the order of the operations of
intersection and radicalization can be exchanged, that is,

$\sqrt{I}\cap\sqrt{J}=\sqrt{I\cap J}.$ (143)

###  A.2 Product of ideals

The product of two ideals $I$ and $J$ in the polynomial ring
$K[X_{1},\dots,X_{n}]$, denoted by $I\cdot J$, is an ideal generated by the
product of the generators of $I$ and $J$. Namely, if $G_{1},\dots,G_{r}$ and
$H_{1},\dots,H_{s}$ generates $I$ and $J$, respectively, then the polynomials
$G_{i}H_{j}$ with $i\in\\{1,\dots,r\\}$ and $j\in\\{1,\dots,s\\}$ generate
$I\cdot J$. That is,

$I\cdot J\equiv\left\\{\sum_{i,j}P_{i,j}G_{i}H_{j}|P_{i,j}\in
K[X_{1},\dots,X_{n}]\right\\}.$ (144)

It is easy to show that

${\bf V}(I\cdot J)={\bf V}(I)\cup{\bf V}(J)={\bf V}(I\cap J),$ (145)

that is, the algebraic set associated with $I\cdot J$ is equal to the union of
the algebraic sets associated with $I$ and $J$. Thus, the multiplication of
ideals acts on the associated algebraic sets like the intersection of the
ideals. The relation between product of radical ideals and their intersection
is given by the equation

$I,J\text{ radical ideals }\Rightarrow I\cap J=\sqrt{I\cdot J}.$ (146)

In general, we have

$\sqrt{I}\cap\sqrt{J}=\sqrt{I\cap J}=\sqrt{I\cdot J}.$ (147)

On one side, multiplication of ideals has the advantage of being much simpler
than intersection. On the other side, the product of radicals is not generally
a radical ideal. As we will see, the intersection of ideals can have fewer
generators with lower degree than the product. Furthermore, the intersection
contains all the polynomials that are zero in the associated algebraic set,
which can be a desired property.

##  Appendix B Linear-algebra tools

In this appendix, we discuss some direct consequences of Jordan’s theorem that
are used in Sec. V. Every $n\times n$ square matrix ${\bf M}$ can be
transformed to a Jordan normal form over an algebraically closed field through
a basis change. This means that there is a basis of vectors grouped in $m$
sets $\\{\vec{v}_{1,k}|k\in\\{1,\dots,n_{1}\\}\\}$,
$\\{\vec{v}_{2,k}|k\in\\{1,\dots,n_{2}\\}\\},\dots$,
$\\{\vec{v}_{m,k}|k\in\\{1,\dots,n_{m}\\}\\}$ with $\sum_{k=1}^{m}n_{m}=n$
such that the application of ${\bf M}$ acts as follows

$\left\\{\begin{array}[]{l}\hat{M}\vec{v}_{s,k}=\lambda_{s}\vec{v}_{s,k}+\vec{v}_{s,k+1}\;\;\;k\in\\{1,\dots,n_{s}-1\\}\\\
\hat{M}\vec{v}_{s,k}=\lambda_{s}\vec{v}_{s,k}\;\;\;k=n_{s}\end{array}\right.$
(148)

In particular, if $n_{s}=1$ for every $s$, then the matrix is diagonalizable.
The existence of this basis is stated by Jordan’s theorem.

Let us apply Jordan’s theorem to the following equation

${\cal A}\vec{w}_{k}={\cal
B}\sum_{l=1}^{n}\lambda_{k,l}\vec{w}_{l}\;\;\;\;k\in\\{1,\dots,n-\delta\\},$
(149)

where $\delta\in\\{0,\dots,n-1\\}$. The vectors
$\vec{w}_{1},\dots,\vec{w}_{n}$ are linearly independent, on which the
matrices $\cal A$ and $\cal B$ act. The task is to find a set
$\\{\vec{w}_{1},\dots,\vec{w}_{n}\\}$ satisfying Eq. (149), given $\cal A$ and
$\cal B$. In the following, we denote by boldface characters matrices acting
on the labels of the vectors $\vec{w}_{k}$. That is, $\bf A$ denotes an
$i\times j$ matrix transforming a set of vectors
$\vec{w}_{1},\dots,\vec{w}_{j}$ to the set of vectors $\sum_{l}{\bf
A}_{1,l}\vec{w}_{l},\dots,\sum_{l}{\bf A}_{i,l}\vec{w}_{l}$. The $n\times n$
matrices acting on the vectors $\vec{w}_{k}$ are denoted by calligraphic
characters. The left-hand side of Eq. (149) has only vectors $\vec{w}_{k}$
with $k\in\\{1,\dots,n-\delta\\}$. Thus, a transformation $\bf T$ on
$\vec{w}_{k}$ preserves the form of the equation if the matrix has the form

${\bf T}=\left(\begin{array}[]{cc}{\bf R}&{\bf 0}\\\ {\bf S}&{\bf
D}\end{array}\right),$ (150)

where $\bf R$, $\bf S$, and $\bf D$ are $(n-\delta)\times(n-\delta)$,
$\delta\times(n-\delta)$, and $\delta\times\delta$ matrices, respectively. Let
us define the basis of vectors

$\vec{v}_{k}\equiv\sum_{l=1}^{n}{\bf
T}_{k,l}\vec{w}_{l}\;\;\;\;k\in\\{1,\dots,n\\}.$ (151)

Denoting by $\lambda$ the $(n-\delta)\times n$ matrix with elements
${\lambda}_{k,l}$, the change of basis from $\vec{w}_{k}$ to $\vec{v}_{k}$
takes to the transformation

${\bf\lambda}\rightarrow{\bf R}{\bf\lambda}{\bf T}^{-1}.$ (152)

Jordan’s theorem implies that there are $m$ sets of vectors
$\\{\vec{v}_{1,k}|k\in\\{1,\dots,n_{1}\\}\\}$,
$\\{\vec{v}_{2,k}|k\in\\{1,\dots,n_{2}\\}\\},\dots$,
$\\{\vec{v}_{m,k}|k\in\\{1,\dots,n_{m}\\}\\}$ such that

$\begin{array}[]{ll}s\in\\{1,\dots,\delta\\}:&{\cal A}\vec{v}_{s,k}={\cal
B}\vec{v}_{s,k+1}\;\;\;k\in\\{1,\dots,n_{s}-1\\}\\\
s\in\\{\delta+1,\dots,m\\}:&\left\\{\begin{array}[]{l}{\cal
A}\vec{v}_{s,k}={\cal
B}(\lambda_{s}\vec{v}_{s,k}+\vec{v}_{s,k+1})\;\;\;k\in\\{1,\dots,n_{s}-1\\}\\\
{\cal A}\vec{v}_{s,n_{s}}={\cal
B}\lambda_{s}\vec{v}_{s,n_{s}}\end{array}\right.\end{array}$ (153)

with

$s\in\\{1,\dots,\delta\\}\left\\{\begin{array}[]{l}\vec{v}_{s,k}\in\text{span}\\{\vec{w}_{1},\dots,\vec{w}_{n-\delta}\\}\;\;\;k\in\\{1,\dots,n_{s}-1\\}\\\
\vec{v}_{s,n_{s}}\notin\text{span}\\{\vec{w}_{1},\dots,\vec{w}_{n-\delta}\\}.\end{array}\right.$
(154)

If the matrix $\cal B$ is invertible, these equations provide a simple way for
building the vectors $\vec{v}_{s,k}$. We have that the vectors take the form

$\left.\begin{array}[]{ll}s\in\\{1,\dots,\delta\\}:&\;\;\vec{v}_{s,k}=({\cal
B}^{-1}{\cal A})^{k-1}\vec{v}_{s}\\\
s\in\\{\delta+1,\dots,m\\}:&\left\\{\begin{array}[]{l}\vec{v}_{s,k}=({\cal
B}^{-1}{\cal A}-\lambda_{s})^{k-1}\vec{v}_{s}\\\ ({\cal B}^{-1}{\cal
A}-\lambda_{s})^{n_{s}}\vec{v}_{s}=0\end{array}\right.\end{array}\right\\}\;\;\;k\in\\{1,\dots,n_{s}\\},$
(155)

where $\vec{v}_{1},\dots,v_{m}$ are free vectors. Let us take ${\cal
B}^{-1}{\cal A}$ is diagonalizable. Thus, the last line is equivalent to the
equation

$({\cal B}^{-1}{\cal
A}-\lambda_{s})\vec{v}_{s}=0\;\;\;s\in\\{\delta+1,\dots,m\\}$

so that $\vec{v}_{s,k}=0$ for $k\in\\{2,\dots,n_{s}\\}$. Since the vectors
$\vec{v}_{s,k}$ are linearly independent and, thus, different from zero, we
must have

$n_{s}=1\;\;\;s\in\\{\delta+1,\dots,m\\}.$

Thus, the general solution is given by the set of vectors
$\\{\vec{v}_{s,k}|s\in\\{1,\dots,\delta\\},k\in\\{1,\dots,n_{s}\\}\\}$ and
$\vec{v}_{\delta+1},\dots,\vec{v}_{m}$ defined by the equations

$\left\\{\begin{array}[]{ll}s\in\\{1,\dots,\delta\\}:&\;\;\vec{v}_{s,k}=({\cal
B}^{-1}{\cal A})^{k-1}\vec{v}_{s}\;\;\;k\in\\{1,\dots,n_{s}\\},\\\
s\in\\{\delta+1,\dots,m\\}:&\;\;({\cal B}^{-1}{\cal
A}-\lambda_{s})\vec{v}_{s}=0\end{array}\right.$ (156)

with

$m-\delta+\sum_{s=1}^{\delta}n_{s}=n.$

## References

  * (1) R. Crandall, C. Pomerance, ”Prime numbers: a computational perspective” 2nd edition, Springer, 278-301 (2001).
  * (2) J. M. Pollard, ”A monte carlo method for factorization”, BIT 15, 331-334 (1975).
  * (3) J. M. Pollard, ”Theorems of factorization and primality testing”, Proceedings of the Cambridge Philosophical Society 76, 521-528 (1974).
  * (4) H. C. Williams, ”A p+1 method of factoring”, Mathematics of Computation 39, 225-234 (1982).
  * (5) E. Bach, J. Shallit, ”Factoring with cyclotomic polynomiasls”, Mathematics of Computation 52, 201-219 (1989).
  * (6) H. W. Lenstra, ”Factoring integers with elliptic curves”, Annals of Mathematics 126, 649-673 (1987).
  * (7) C. Pomerance, ”The quadratic sieve factoring algorithm”, Advances in Criptology, 169-182 (1984).
  * (8) Y. Aubry, M. Perret, ”A Weil theorem for singular curves”, in Arithmetic, Geometry and Coding Theory, 1-7 (de Gruyter, Berlin , 1996).
  * (9) F. Rouillier, ”Solving zero-dimensional systems through the rational univariate representation”, Applicable Algebra in Engineering, Communication, and Computing, 9(5), 433–461, (1999).
  * (10) N. M. Katz, ”The work of Pierre Deligne”, Proceedings of the International Congress of Mathematicians, 47-52 (Helsinki, 1978).
  * (11) A. Seidenberg, ”Constructions in algebra”, Trans. Amer. Math. Soc. 197, 273-313 (1974).
  * (12) T. H. Nguyen, ”Combinations of Boolean Gröbner bases and SAT solvers”, Phd thesis at Technische Universität Kaiserslautem, 2014.