Application:
We intend to factor an integer $N$ using a variation of the rational sieve.
This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ where $x$,$y$ are $B$-smooth. The standard method to obtain such relations is to traverse $f(x) = x - N$ using a highly-optimized Sieve of Eratosthenes for all primes $p < B$ to reveal smooth values $y = f(x)$. This is essentially the same method used for the Quadratic Sieve (QS) and the modern General Number Field Sieve (GNFS).
The problem with this method lies in the rapidly vanishing probability of smoothness for large values of $x$ and/or $y$. This requires us to sieve vast ranges of useless integers to obtain a few smooth ones.
Alternatively, there is a way to directly generate smooth relations. Represent $N$ as a sum of $n$ $B$-smooth integers in $m$ different ways, where $n \approx m$. This can be done efficiently using the package-merge algorithm for the coin collector's problem. Then use a specialized linear algebra algorithm to produce an integer linear combination of these sums that has all but two of its addend coefficients equal to zero, thus forming the equation $x + y = zN$. Rearrange this to $x - zN = -y$. Then if the coefficients used to produce $x$,$y$ are on the order of $B$, this provides a smooth relation for our congruence matrix with good probability.
If this can be done efficiently, it would seem to admit a fast method of factoring integers.
\begin{align*} \hline \end{align*}
Definitions:
- Let $\rho(n)$ denote the set of unique prime factors of an integer $n$.
Inputs:
- An arbitrarily large integer $N$ to be factored.
- A smoothness bound $B$ and corresponding factor base $P = \{-1\} \cup \{p \in \mathbb{N} \mid p \leq B \text{, $p$ is prime}\}$.
- An arbitrary finite set of integers $K \subset \mathbb{Z}$ with $k\ \bot\ \ell\ \ \forall\ k,\ell \in K$.
- A vector $s \in \mathbb{Z}^{n}$ with entries comprising $n$ unique addends $s_{j}$, $\rho(s_{j}) \subset P$, $0 < j \leq n$.
- A set of $m$ row vectors $M = \{v_{1}, v_{2}, \dots, v_{m} \in \mathbb{Z}^{n+1} \mid \rho(v_{ij}) \subset P,\ \forall i\leq m, j\leq n\}$, forming an $m \times (n + 1)$ matrix of integer coefficients $v_{ij}$ initialized such that $$\sum_{j=1}^{n} v_{ij}s_{j} = v_{i,n+1}N$$ for each row vector $v_{i}$. In practice, $m \approx n$.
For example, suppose $N = 14$ and $s = [2^{0}, 2^{1}, 2^{2}, 2^{3}]$; then we could have a row $v_{0} = [0, 1, 1, 1, 1]$ corresponding to the binary representation of $1N$. In practice, $s$ could comprise any variety of $B$-smooth integers.
Desired Output:
- A row vector $w \in \mathbb{Z}^{n+1}$ that is an integer linear combination of the vectors in $M$ that has all of its first $n$ entries equal to zero except for two, and has its last entry $w_{n+1}$ either 1, prime, or coprime to every element $k \in K$.
In practice, we insert $w_{n+1}$ into $K$ after each execution of the algorithm for a given $N$.
\begin{align*} \hline \end{align*}
Example Input:
$$N = 35$$ $$B = 13$$ $$K = \varnothing$$ $$s = [3^2, 2^5, 2^4, 2^3, 2^2, 2^1, 2^0]$$
\begin{align*} M = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & -1 & -1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & -1 & 1 & 1 \\ -4 & 3 & -1 & -1 & 0 & 0 & -1 & 1 \\ 4 & 0 & 0 & 0 & 0 & 0 & -1 & 1 \\ \end{bmatrix} \end{align*}
\begin{align*} \hline \end{align*}
Example output 1: $w = [2, 6, 0, 0, 0, 0, 0, 6] \implies (2)3^2 + (6)2^5 = (6)35$
Example output 2: $w = [-13, 0, 0, 0, 0, 6, 0, -3] \implies (-13)3^2 + (6)2^1 = (-3)35$
Example output 3: $w = [0, 4, 0, 0, 0, 6, 0, 4] \implies (4)2^5 + (6)2^1 = (4)35$
\begin{align*} \hline \end{align*}
Question:
Given inputs $N$, $B$, $K$, $s$, and $M$, what is the maximum number of arithmetic steps required to find an output or to determine that none exists? Essentially, I am looking for an efficient algorithm or heuristic and its worst-case time complexity. The "specialized linear algebra algorithm" I mention in the introduction does not yet exist; it's what I'm trying to find.
Ultimately, we want to obtain the set of all unique outputs mutually respecting the constraint on $w_{n+1}$.
