Suppose $n$ is an integer and we wish to factor it. As a special case we have $n = pq$ with $p,q$ distinct primes. The problem: factoring $n$ via complex analysis tools
Background
I have been interested in integer factorization for some time now. Recently I have been trying to apply generating function type of stuff to the problem with no success. I tried coming up with all sorts of function that would be somehow 'nice enough' so that factoring could be done analytically through them. I failed and all I could come up with were functions that were simple but unwieldy as trial division (encoded via sums of Kronecker deltas) or functions that need one or more of the factors of of $n$, which does not help. Then a few days ago, I had sort of a breakthrough. I realized that the following function's zeros are the divisors of $n$. Let
$f_n(z) = 2 – \cos(2\pi z) – \cos(\frac{2 \pi n}{z})$
It is easy to see that this function has real zeros precisely at the divisors of $n$ (both negative and positive) and is $> 0$ otherwise. And of course, one can apply complex analysis to this to find those zeros. Once I found this function I found a paper (can read here http://sqig.math.ist.utl.pt/pub/MateusP/11-MV-qsec12.pdf) detailing the use of a function analogous to the one I found in trying to factor numbers via complex integration.
A method
Here is one of the methods outlined in the paper. It gives the jist of the commonalities of the methods stated. In RSA $p \neq q$, so one of them is smaller than $\sqrt{n}$ and the other is larger. Suppose that $q > \sqrt{n}$. Let $h_n(z) = 1/f_n(z)$. The only pole of $h_n(z)$ in $I = [\sqrt{n},n)$ is $z = q$ of order 2 and there are no more in that interval. One can calculate the residue of $h_n(z)$ at $z = q$ by computing
$\frac{1}{2\pi\,i} \int_{\gamma} h_n(z) dz$
where $\gamma$ has the following properties:
- it circles once around the integers in $I$
- it contains none of the complex zeros of $f_n(z)$ that are off the real axis
The resulting residue is in terms of $n$ and $q$ and given an approximation to the residue, one can solve numerically to find $q$. Now the problem reduces to a numerical calculation of a contour integral.
One of the benefits of such an approach is that the contour can be split up in many pieces to be distributed in a parallel computing scheme to calculate it fast leading to only having a small sequential part. However, the major downside seems to be in the highly oscillatory nature of the function involved. I implemented the numerical integration and even though it works, it seems quite slow.
Questions
-
Do you know of any recent work on this problem?
-
Are there integer factorization algorithms besides the ones outlined in the paper that use complex integration?
-
Since the main impediment seems to be the oscillatory nature of functions like $f_n(z)$, then can we 'smoothen' the oscillations to make integration easier?
-
If not, can we somehow use the repetition to speed up the numerical integration?
A solution $g_n(z)$ to the last two questions will preferably satisfy the following conditions
- $g_n$ only takes $n$ and $z$ as input
- $g_n$ has zeros, poles, or maxima (or other distinguished points) at the divisors of $n$
- these distinguished points are the only ones on the real axis or if there are more, they are easy to classify and thus cancel out
Best Answer
I can give you a negative answer and a kind of a positive answer to your question. First, similar to what Henry Cohn says, the conventional view of your construction is that it is a restatement of the factoring problem rather than a step to an algorithm. A function with a lot of oscillation is at first glance a function with high information content. So the fact that your setup is numerical rather than discrete doesn't necessarily help anything. In fact, standard numerical integration methods won't look all that different from trial division. Of course it is impossible to rule out some excellent special-purpose numerical integration method, especially because if you apply your transformation backwards, any factoring algorithm is such a special method. And in my opinion subexponential factoring algorithms are a little bit miraculous. You suggest setting up factoring as a 1-dimensional integration problem. But I know of very few numerical analysis algorithms that give a more-than-polynomial gain in speed over obvious algorithms in low dimensions. The main example that comes to mind is spectral methods for solving differential equations or integrals to high accuracy --- but that already starts to look like your construction in reverse.
On the positive side, Shor's quantum algorithm for factoring does look a little bit like your oscillation picture. The algorithm does not look for an oscillation frequency that matches a factor of the number $n$. Instead, it computes the exponents of elements in $(\mathbb{Z}/n)^\times$, which is enough to factor $n$ when $n$ is odd. Using $a^x$ as a periodic function of $x$, it makes a vector $\psi$ in $L^2(\mathbb{Z})$ which is approximately periodic on a large scale with period the exponent of $a$. It then takes an approximate Fourier transform of this vector, and then measures a Fourier mode $k$ weighted according to the square amplitudes of the transform of $\psi$. So this is extracting information from oscillatory integrals! However, crucially, the integral is "computed" with quantum probability, in only the weak sense that a simulated random walk "computes" return probabilities. Quantum amplitudes are NOT stored numbers, they are probability-like state. So their approximate integration in quantum computation is very restricted. However, you have the exotic advantage of handling exponentially many amplitudes, just as randomized algorithms have probabilistic access to exponentially many possibilities.