Integer Factoring via Lattice Reduction?

Question

I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993. It looks like a probabilistic method with expected polynomial run time (and space) is presented to do integer factorization.

From the paper: "A scenario for factoring $N \approx 2^{512} $ ... The corresponding lattice problem is unfeasible for the presently known lattice reduction algorithms. We have no experience with lattice basis reduction for lattices with dimension 6300. Moreover the bit length of the input vectors is at least 1500."

I take this to mean that the algorithm presented is polynomial but the exponent and factors are so large that it makes it computationally impractical for current technology.

Can anyone weigh in on this? Is this paper legitimate? Isn't this huge news if it is? Doesn't this mean that integer factoring is likely in P? Have people been progressing towards making lattice reduction algorithms more tractable?

Answer 1

I am not an expert in lattice problems, but I do know the exact-case problem, Shortest Vector Problem (SVP), is NP-hard. In this paper, Schnorr appears to reduce integer factorization to some form of the approximation version of Closest Vector Problem ($\gamma$-CVP), where CVP is a generalization of SVP. However, I do not believe there are known polynomial time algorithms for this.

Some known facts about $\gamma$-CVP:

Arora, et al (PDF), show that approximating the closest vector within any constant is NP-hard.

Also, they show that, for $\epsilon > 0$, if you can approximate the closest vector within a factor of $2^{\log^{\frac{1}{2} - \epsilon}{n}}$ in polynomial time, then any problem in NP can be solved in quasi-polynomial time.

Dinur, et al (ACM Citation), later strengthened the inapproximability result to:

For $\epsilon > 0$, approximately finding the closest vector within a factor $n^{\frac{\epsilon}{\log\log{n}}}$ is NP-hard.

Although I'm unfamiliar with Schnorr's work, what we know of lattice problems would lead me to believe that this is not intended to lead to a polynomial-time algorithm directly. Rather, Schnorr spends some deal of time talking about actual implementations (e.g. running this program on such-and-such computer takes approximately so many weeks/months/years/eons).

P.S. As Suresh points out, it appears to be an effort to get "quick enough" or "quicker" run times for integer factorization, despite the complexity.

P.P.S. And if I can make a further conjecture: Given that Schnorr's paper pre-dates the work on hardness of approximating lattice problems, it's likely that there was some original hope that it might have led to a polynomial-time algorithm for integer factorization. In light of Arora et al and Dinur et al, however, it's clear that there's not a solution (or at least, a straightforward solution) along that route, however.

Answer 2

The paper presents a reduction from factoring to a lattice problem. It doesn't go on to claim that the lattice problem can be solved in (probabilistic) polynomial time. My understanding is that Schnorr's assertion instead is that fast implementations for finding short vectors in lattices (independently studied, like LLL etc) can then be employed for fast implementations of factoring solutions (akin in spirit to how SAT solvers can often be used as a fast subroutine for solving other hard problems)