Devising an Algorithm for Linear Combination with Column Restrictions

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}$.

Your problem can be solved in about $O(n^3 \log(nB))$ time on average, using the following procedure:

• Guess the two indices of the two non-zero entries. In other words, guess indices $y,z$ such that $w_i =0$ for all $i \notin \{y,z\}$.

• Find an integer linear combination of the vectors in $M$ that are zero in all of the first $n$ positions except for $y,z$. Note that this can be done using Gaussian elimination: each position that must be zero corresponds to a linear equation, and we have $n-2$ linear equations in $m$ unknowns. If a non-trivial solution exists, Gaussian elimination can find it. When $m \ge n-2$, this is expected to have a non-trivial solution with high probability, under a heuristic assumption that the matrix entries are random. More specifically, I recommend that you throw away the last column of the matrix and work with integers modulo $N$. Then, you're looking for an integer linear combination of vectors that are non-zero modulo $N$ in all of the first $n$ positions except for $y,z$. Gaussian elimination can be done modulo $N$, and any solution modulo $N$ can be extended to one over the integers (by adjusting the last column, you can add or subtract an appropriate multiple of $N$ so that everything works out over the integers).

• Check that the resulting $w_{n+1}$ is either prime or co-prime to everything in $K$.

What's the running time of this procedure? The Gaussian elimination step takes $O(n^3)$ time. With constant probability, there exists a non-trivial solution to the set of linear equations. Finally, a random integer is prime with probability at least $1/\log(nB)$ (by the prime number theorem, and using that the last entry of $w_{n+1}$ is at most $nB$), so heuristically, we expect the last step to succeed with probability about $1/\log(nB)$. Therefore, with $O(\log(nB))$ iterations, we expect to find a solution that satisfies all of the conditions. Each iteration takes $O(n^3)$ time, so the total running time is $O(n^3 \log(nB))$.

I don't know whether this can be improved.

P.S. Why is $w_{n+1}$ at most $nB$? Well, from the integer linear combination modulo $N$, we get $w_1,\dots,w_n$ that satisfy

$$\sum_{j=1}^n w_j s_j = 0 \pmod N.$$

By letting $w_{n+1} = -(\sum_{j=1}^n w_j s_j)/N$, we thereby find a vector $w$ that satisfies

$$\sum_{j=1}^n w_j s_j = w_{n+1} N,$$

which is a solution of the desired form. Now how large can $w_{n+1}$ be? Well, bounding each term in the sum and using that $w_1,\dots,w_n$ were reduced modulo $N$, we find

$$|\sum_{j=1}^n w_j s_j| \le \sum_{j=1}^n |w_j s_j| \le \sum_{j=1}^n NB = nNB.$$

It follows that $|w_{n+1}| \le nB$.

• Wow, this might seem dumb, but I honestly hadn't thought of making equations for the $w_{i}$ = 0's. Guess it was under a nose-hair. Seriously, thanks a lot for that. Also, it might not be bad to just guess $y$,$z$ as you said, since I can keep the column fill rate roughly balanced. – user35908 Jul 28 '15 at 6:38
• @jrodatus, Thanks for the helpful feedback. I've elaborated my answer significantly to explain how you can bound $w_{n+1}$. It involves first working modulo $N$, then extending the solution to the integers. I made changes 2 the second bullet and the running time analysis after the method. – D.W. Jul 28 '15 at 7:53
• Cool- the $\pmod N$ trick is pretty clever. Your answer makes me realize I forgot to include the post-condition that $w_{y},w_{z}$ be smooth, but there could be at least two conceivable ways for me to achieve this without any modification to your solution... 1) $s$ and $M$ can be chosen carefully so that the entries in $M$ are small compared to $B$, or 2) the chosen non-zero columns $w_{y},w_{z}$ might be intelligently set to some smooth values when solving... will have to run some tests. – user35908 Jul 28 '15 at 16:20
• @jrodatus, got it. Assuring smoothness might be a lot harder - my approach might be dead in the water, as far as that additional condition. – D.W. Jul 28 '15 at 16:26
• "Probably" smooth would be sufficient; you've given me some great tools to work with that I probably wouldn't have thought of (including a proper way to define the problem), and I'm appreciative for the time you took to do that. Frankly I wish someone could just point out "Bud, this'll never work and here's why..." so I don't waste my time, but in the absence of that, curiosity has got the better of me. For that reason, if I do post again it'll probably be on crypto like you said. – user35908 Jul 28 '15 at 16:53