<p>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 <strong>implementations</strong> for finding short vectors in lattices (independently studied, like LLL etc) can then be employed for fast <strong>implementations</strong> of factoring solutions (akin in spirit to how SAT solvers can often be used as a fast subroutine for solving other hard problems)</p>

CC BY-SA 2.5
2010-09-14T16:42:59.487Z
2010-09-14T16:42:59.487Z
Suresh Venkat
<p>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.</p>

<p>Some known facts about $\gamma$-CVP:</p>

<p>Arora, et al (<a href="http://www.di.ens.fr/~stern/data/St49b.pdf">PDF</a>), show that approximating the closest vector within any constant is NP-hard. </p>

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

<p>Dinur, et al (<a href="http://portal.acm.org/citation.cfm?id=1005180.1005182">ACM Citation</a>), later strengthened the inapproximability result to:</p>

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

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

<p>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>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.</p>

CC BY-SA 2.5
2010-09-14T22:46:05.463Z
Thank you.  I know that in many cases, though LLL has an exponential bound to within optimal, it often does much better in practice.  Has anyone tried using this method to see how close they get to factoring integers?
user834
CC BY-SA 2.5
2010-09-14T16:44:58.763Z
2010-09-14T16:56:00.910Z
2010-09-14T16:56:00.910Z
Daniel Apon
<p>I found a paper titled "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.9005&amp;rep=rep1&amp;type=ps" rel="noreferrer">Factoring integers and computing discrete logarithms via diophantine approximation</a>" 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.</p>

<p>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."</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 4.0
2018-10-01T17:19:43.553Z
See: https://arxiv.org/pdf/1003.5461.pdf for a follow up article.
O. S. Dawg
<ds.algorithms><approximation-algorithms><integer-programming>
Integer Factoring via Lattice Reduction?
user834
# Integer Factoring via Lattice Reduction?

(Asked by: username_0 on 2010-09-14)

I found a paper titled "[Factoring integers and computing discrete logarithms via diophantine approximation](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.9005&rep=rep1&type=ps)" 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?

**Tags:** ds.algorithms, approximation-algorithms, integer-programming
> **Comments:**
> **username_1**: See: https://arxiv.org/pdf/1003.5461.pdf for a follow up article.  

---

## 2 answers

### Answer by username_3 on 2010-09-14. Score: 12 | Accepted answer

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](http://www.di.ens.fr/~stern/data/St49b.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](http://portal.acm.org/citation.cfm?id=1005180.1005182)), 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.

> **Comments:**
> **username_0**: Thank you.  I know that in many cases, though LLL has an exponential bound to within optimal, it often does much better in practice.  Has anyone tried using this method to see how close they get to factoring integers?  

---

### Answer by username_2 on 2010-09-14. Score: 10

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)


---

