18
$\begingroup$

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

  1. Do you know of any recent work on this problem?

  2. Are there integer factorization algorithms besides the ones outlined in the paper that use complex integration?

  3. 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?

  4. 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
$\endgroup$
4
  • 1
    $\begingroup$ That's a nice observation about the function $f_n$, but unfortunately I don't think it will help with efficient factorization. The contour will be exponentially long (compared with the number of digits in $n$) if you choose it to be connected, or it will have exponentially many pieces if you make a small loop around each integer. Either way, you need to find the one part that actually contributes something in an exponentially long calculation, and I don't think complex analysis offers any good algorithms for this. $\endgroup$
    – Henry Cohn
    Jun 6, 2011 at 12:13
  • 12
    $\begingroup$ Instead, I'd view this in the opposite direction, as a hardness proof: finding roots of simple closed-form functions is as hard as factoring. In fact, it's known that there's no algorithm to decide whether a given function has a real root, for functions derived by addition, multiplication, and composition from the identity function, rational numbers, pi, and the sine function; this was proved by Wang, based on results of Richardson. However, the constructions needed to prove it are much more elaborate. The function $f_n$ is not in this class, but it's very simple, so it is a good example. $\endgroup$
    – Henry Cohn
    Jun 6, 2011 at 12:29
  • $\begingroup$ Actually, if we use the argument principle by premultiplying the $f'(z)/f(z)$ by $z^k$, the integral evaluates to $2q^k$ and at least for $k = 1$, the big part of the integral is the part that runs parallel to the real axis (if we are using a rectangular contour). So that's bad news. $\endgroup$ Jun 6, 2011 at 13:41
  • 6
    $\begingroup$ Kamel Bentahar studied this very function in his masters thesis in 2004, and Daniel Brown has also thought along these lines (eprint.iacr.org/2008/149), but without success, concluding that the method is probably doomed to fail. $\endgroup$
    – Granger
    Jun 6, 2011 at 15:25

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

It won't work. If you integrate round something which looks like (1/z), you'll get a finite residue. BUT if you integrate round 1/f(z), which looks like (1/z^2) at the zeroes of your function, you'll get zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.