Can spatial filters be used to factor composite numbers?

Question

$Z=(N-XY)^2$ is a surface with absolute minima ($0s$) anywere $Y=N/X$.

I know this question is naiive, but shouldn't it be possible to apply a lossy compression filter to this function which preserves values only at discrete boundaries and then search for absolute minima?

If the answer is no, is there any online reference which describes the difficulties of this approach?

---

POSTSCRIPT

Some things crystalised in the discussion below, and need more space than can be added in the comments.

First, this question originates from the interaction of 3D rendering software and its interaction with the function $Z=(N-XY)^2$ (tested for small N only). The interaction results in a surface denoted by $LC(x,y)$ below.

Now let $f(x)=N/x$, and $m(x)=\frac{df}{dx}=-N/x^2$, then the line normal to $f(x)$ at $\mathbf{x^\prime}$ is:

$$(y-f(\mathbf{x^\prime})) + (x-\mathbf{x^\prime})/m(\mathbf{x^\prime}) = 0$$

Expressing $y$ as a function of $x$:

$$y(x) = \frac{N^2-\mathbf{x^\prime}^4}{N\mathbf{x^\prime}} + x\frac{\mathbf{x^\prime}^2}{N} $$

Let the mouth of the valley below $\{\mathbf{x^\prime},f(\mathbf{x^\prime}),z\}$ be:

$$ r(\mathbf{x^\prime},z)=\sqrt{(x-\mathbf{x^\prime})^2+(y(x)-f(\mathbf{x^\prime}))^2} \,\,\, \text{where} \,\, LC(x,y(x))=z $$

What is the likelihood of finding a suitable function $LC(x,y)$ such that $r(\mathbf{x^\prime},z)$ is maximum when $\mathbf{x^\prime}$ and $f(\mathbf{x^\prime})$ are integers?

Some things to note about $LC(x,y)$ and $r(\mathbf{x^\prime},z)$

• $r(\mathbf{x^\prime},0) = 0$ iff $\{\mathbf{x^\prime},f(\mathbf{x^\prime}),0\}$ is rendered (i.e. sampled); otherwise $r(\mathbf{x^\prime},0)$ is undefined.
• $r(\mathbf{x^\prime},z)$ is defined for $z>=z_{sat}$ where $z_{sat}$ is implementation dependent.
• if $LC(x,y)$ is perfectly lossless, then $r(\mathbf{x^\prime},z)$ can be computed for all positive $\mathbf{x^\prime}$ and $z$ by solving the quadratic: $$\sqrt{z}-N+x\frac{N^2-\mathbf{x^\prime}^4}{N\mathbf{x^\prime}} + x^2\frac{\mathbf{x^\prime}^2}{N}=0$$

Answer 1

There are some good reasons why this hasn't been tried.

Firstly, it's not "discrete boundaries" but all points with integer coordinates $(x,y)$ on the hyperbola $xy=N$ which are candidates for factorization. The only information that matters is in those points, it doesn't matter if one uses your $$ (N-xy)^2 $$ and look for zeroes, or if one uses $$ (N/x)-\lfloor N/x\rfloor $$ and looks for zeroes.

Secondly the function will be horribly noisy, and given our statistical knowledge about primes on the coarse scale, it is unlikely that it can be compressed much. The spatial filters can only use global, coarse information, otherwise they have to behave like functions that depend on brute force searching, in which case one might as well throw out the function, and the filter and the complications it represents, and work directly with discrete objects, i.e., integers, number fields, etc.

Finally, the state of the art factoring algorithms use a lot information from statistical as well as algebraic domains to optimize their execution complexity, but still have huge complexity, simply because $N$ is too large, and for the case we're interested in, $N=xy$ has ONLY one solution: This is when $x,y$ are two primes of roughly equal size.

Answer 2

The angel on my other shoulder says the following:

Every polynomial-form approach to finding the factors of a numbers ultimately boils down to a search for integer solutions to the radical expression:

$$ \epsilon = \varepsilon \pm{} \sqrt{\xi^2 \pm N} $$

and so the use of quadratic or cubic spatial interpolation and filtering will inevitably lead to a circular argument.

Answer 3

According to Wolberg monotonic interpolation techniques exist which can reduce the oscillation seen in the graph mentioned in the the question's postscript.

I'm not going to discuss Wolberg's method, but I will use background information from his paper to compute a formula for the original graph. Depending on how it all goes, I leave it to the reader to follow-up with techniques that remove localized minima.

Difference Equations for the Formula

It is useful to express sampled continuous functions as difference equations when analysing them as discrete functions. The equation $f_x = (N-xy)^2$ can be expressed as a difference equation as shown by the following derivation:

\begin{eqnarray} (1) & (N - (x+2U)*y)^2 - (N-xy)^2 & = & -4UNy - 4xUy^2 - 4(Uy)^2\\ (2) & (N - (x+U)*y)^2 - (N-xy)^2 & = & -2UNy - 2xUy^2 - (Uy)^2\\ (1),(2) & f_{i+2}-f_i & = & \hspace{1em} 2 ( f_{i+1} - f_i ) - 2U^2y^2\\ & f_{i+2} - 2 f_{i+1} + f_i + 2U^2y^2 &=& 0 \\ & f_{i+2} - 2 f_{i+1} + f_i + 2N^2\Upsilon^2 &=& 0\hspace{1em} [\textrm{where } \Upsilon=Uy/N,\hspace{1ex} 0<=\Upsilon<=1] \end{eqnarray}

Spline Interpolation

Connecting each point $(i*U,f_i)$ to its neighbor $((i+1)*U,f_{i+1})$ is a polynomial $p_i$ such that:

$$p_i(x) = a_i(x-Ui)^3 + b_i(x-Ui)^2 + c_i(x-Ui) + d_i$$

where

\begin{eqnarray} a_i&=&\frac{1}{U^2}\left(-2\frac{-2UNy - 2i(Uy)^2 - (Uy)^2}{U}+2y(N-iUy)+2y(N-(i+1)Uy)\right)\\ b_i&=&\frac{1}{U}\left(3\frac{-2UNy - 2i(Uy)^2 - (Uy)^2}{U}-4y(N-iUy)-2y(N-(i+1)Uy)\right)\\ c_i&=&-2y(N-iUy)\\ d_i&=&(N-iUy)^2 \end{eqnarray}

Simplifying

\begin{eqnarray} a_i&=&\frac{1}{U}\left(-2\frac{-2\Upsilon - (2i+1)y^2}{1}+4\Upsilon-(4i+2)y^2\right)\\ &=& 8\Upsilon/U\\ b_i&=&\frac{1}{1}\left(3\frac{-2\Upsilon - (2i+1)y^2 }{1}-6\Upsilon+(6i+2)y^2\right)\\ &=& -12\Upsilon-y^2\\ c_i&=&-2Ny(1-i\Upsilon)\\ d_i&=&N^2(1-i\Upsilon)^2 \end{eqnarray}

yielding

\begin{eqnarray} p_i(x) &=& 8\Upsilon/U(x-Ui)^3 & -\\ & & (12\Upsilon+y^2)(x-Ui)^2 & -\\ & & 2Ny(1-i\Upsilon)(x-Ui) & +\\ & & N^2(1-i\Upsilon)^2 &\\ &=& (8\Upsilon{}x/U-\Upsilon{}(8i+12)-y^2)(x-Ui)^2 & -\\ & & (1-i\Upsilon)(2Nyx-N^2\Upsilon{}i-N^2) & \end{eqnarray}

Furthermore, let $x=Ui+U/2=U/2(2i+1)$:

\begin{eqnarray} p_i &=& (8\Upsilon{}x/U-\Upsilon{}(8i+12)-y^2)(U/2)^2 -\\ & & (1-i\Upsilon)(2Nyx-N^2\Upsilon{}i-N^2) \\ &=& (8\Upsilon{}(2i+1)/2-\Upsilon{}(8i+12)-y^2)(U/2)^2 -\\ & & (1-i\Upsilon)(NUy(2i+1)-N^2\Upsilon{}i-N^2) \\ &=& (\Upsilon{}/2-\Upsilon{}(12)-y^2)(U/2)^2 -\\ & & (1-i\Upsilon)(N^2\Upsilon(2i+1)-N^2\Upsilon{}i-N^2) \\ &=& -\Upsilon{}(2y^2+25)(U^2)/8 -\\ & & N^2(1-i\Upsilon)(\Upsilon(i+1)-1) \\ &=& N^2\left(-\Upsilon{}(2\Upsilon{}^2+25(U/N)^2)/8 + (i\Upsilon-1)(i\Upsilon-1 +\Upsilon) \right)\\ &=& N^2\left(-\Upsilon{}(2\Upsilon{}^2+25(U/N)^2)/8 + (i\Upsilon-1)^2 +(i\Upsilon-1) \right)\\ &=& N^2\left(-2\Upsilon{}^3+ i^2\Upsilon^2-\left(\frac{25(U/N)^2}{8} + i\right)\Upsilon{} \right) \end{eqnarray}

Finally, let's choose U=1.

\begin{eqnarray} p_i &=& N^2\left(-2\Upsilon{}^3+ i^2\Upsilon^2-\left(\frac{25}{8N^2} + i\right)\Upsilon{} \right)\\ p_i &=& -2\Upsilon{}^3+ i^2\Upsilon^2-\left(\frac{25}{8N^2} + i\right)\Upsilon{} \\ p_i &=& 2\Upsilon{}^2 - i^2\Upsilon + \left(\frac{25}{8N^2} + i\right) \\ p_i &=& (4N\Upsilon{})^2 - 2i^2(4N\Upsilon) + (25+8iN^2) \end{eqnarray}

Solving for $p_i=z$

Now accept that what we've got is a simple variable substitution of i for x (it may not be, but if not, the closed-form solution of the z-transform of $p_i$ would handle the conversion from a discrete point-cloud to a continuous function).

The sub-goal was to find values of $(x,y(x))$ such that $p(x,y)=z$ for arbitrary values of $z$. Substituting $x$ for $i$, z for $p_i$ and $\frac{N^2-{x^\prime}^4}{N^2x^\prime} + x\frac{{x^\prime}^2}{N^2}$ for $\Upsilon$ yields:

\begin{eqnarray} z &=& (4N(\frac{N^2-{x^\prime}^4}{N^2x^\prime} + x\frac{{x^\prime}^2}{N^2}))^2 -\\ & & 2x^2(4N(\frac{N^2-{x^\prime}^4}{N^2x^\prime} + x\frac{{x^\prime}^2}{N^2})) +\\ & & (25+8xN^2) %4N\Upsilon{} = i^2 \pm \sqrt{i^4- (25+8iN^2)} \\ %4Uy = i^2 \pm \sqrt{i^4- (25+8iN^2)} \\ %4N = i^2 \pm \sqrt{i^4- (25+8iN^2)} \hspace{1em} \text{for } y=V \end{eqnarray}

The quadratic formula can be used to find a real-valued number for $x$ given integer values of $x^\prime$ and $z$.

Finding maxima of $r(x^\prime,z)$

Given $x$, $y(x)$, and $f(x)$, it is now possible to graph $r(x^\prime,z)$. Once I get past the algebra.

$$ r(\mathbf{x^\prime},z)=\sqrt{(x-\mathbf{x^\prime})^2+(y(x)-f(\mathbf{x^\prime}))^2} \,\,\, \text{where} \,\, LC(x,y(x))=z $$