# Can spatial filters be used to factor composite numbers?

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

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.

• Thanks. Your first and last points are clear. A search for the single answer in a raster image is difficult, so the question that remains is 'how complex is the horribly noisy continuous function?' In the plots I have seen, the filtered image has cone-like 'teeth' that rise at roughly the same rate, meaning that their openings (at a nominal height Z) as measured normal to the curve of the 'gumline' depend on their depth. Unfortunately the math is beyond me and better understanding your second point above would convince me that the pursuit would be futile. – zQAycX May 19 '15 at 11:05
• "otherwise they have to behave like functions that depend on brute force searching" That's the part telling you how (in)efficient it is. And brute search is very, very slow, compared to state-of-the-art factorization algorithms. – tylo May 19 '15 at 13:17
• I've edited the question to formalize it somewhat. If I take you at your word that they have to behave that way, then: $LC(x,y)$ is effectively random and needs a search for every value of $x,y$. Also it's likely that $r(x,z)$ has too many localized maxima and finding the absolute maxima is inefficient. Would you suspect both to be true? – zQAycX May 19 '15 at 22:05
• @zQAycX, yes I would suspect both to be true, but I have no proof. – kodlu May 20 '15 at 1:50
• @kodlu I'm willing to accept this as an answer if you can suggest a few search terms or references to help in understanding the design of spatial filters. If it helps, I've added a few observations about $r(\mathbf{x^\prime},z)$ and $LC(x,y)$ to the postscript. Thanks to the moderator for not closing the discussion down. – zQAycX May 20 '15 at 23:30

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.

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

• I'm sure there are algebraic errors here. – zQAycX Jun 15 '15 at 2:47