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