Did Schnorr destroy RSA? Show me the factors
OK, here is a brief overview for people:<p>To factor a number N (assumed to essentially be the product of two very large primes), find a &#x27;short&#x27; lattice vector [0] using LLL [1] (and BKZ reduction? [2]) that finds many relations of the form:<p><pre><code>    (u_i) = p_i,0 * p_{i,1} * ... * p_{i,n-1}
    (u_i - v_i * N) = q_{i,0} * q_{i,1} * ... * q_{i,n-1}
</code></pre>
where p,q are small primes.<p>Numbers that have all their factors less than some prime, B, are said to be &quot;B-smooth&quot;. In the above, both (u_i) and (u_i - v_i * N) are p_{i,n-1}-smooth and q_{i,n-1}-smooth, respectively.<p>Construct many u_i and (u_i - v_i * N), so much so that you can create a product of primes, r_i, of the form:<p><pre><code>    r_0^{2 b_0} * r_1^{2 b_1} * ... * r_{n-1}^{2 b_{n-1}} = 1 mod N
</code></pre>
where each b_i are integers.<p>Since all exponents (2<i>b_i) are even, we have the potential to find the square root of 1 which has the potential to resolve to two different numbers since N is composite. One of those is the product of r_i^{b_i} and the other is -1. Since y^2 = 1 mod N, we get (y-1)</i>(y+1) = 0 mod N. If (y-1) or (y+1) are not 0, then then must share a factor of N and we&#x27;ve successfully factored.<p>The trick is, of course, finding the smooth numbers. To do this, a lattice basis is made such that you find a short integer relation of the form<p><pre><code>    a_0 ln(p_0) + a_1 ln(p_1) + ... + a_{n-1} ln(p_{n-1}) ~= ln(N)
</code></pre>
where ~= means &quot;approximately equal to&quot;.<p>u is chosen as the product of primes of all a_i &gt; 0 and v is chosen to be the product of all primes where a_i &lt; 0. The hope is that (u - v*N) is also p_{n-1}-smooth, which, as far as I understand, most of the math in the paper is trying to justify.<p>The main innovation here, as far as I can tell, is that Schnorr is fiddling with the &#x27;weighting&#x27; of the main diagonal when constructing the lattice basis. I interpret this as basically trying to randomize the initial lattice basis so that the chances of getting a different integer relation (for eventual construction of u,v) is more probable.<p>I&#x27;ve been confused about this for over a decade as variants of this algorithm, and Schnorr&#x27;s work in general, have been well published. For example, there&#x27;s a paper from 2010 on &quot;A Note on Integer Factorization Using Lattices&quot; by Antonio Vera which discusses Schnorr&#x27;s [3] construction.<p>Is Schnorr trying to shout louder so people will listen or is there something else fundamentally flawed with this type of algorithm?<p>Just a word of warning, LLL solves polynomial factorization in polynomial time (given a polynomial with integer coefficients, find it&#x27;s factor polynomials also with integer coefficients) [4] and has been used to break other (now very old) cryptosystems [5]. If there&#x27;s a candidate algorithm to solve integer factoring, lattice reduction (LLL, PSLQ, etc.) are it.<p>I know of fplll that&#x27;s a stand alone (FOSS) implementation of LLL and some extensions (BKZ, etc.) [6].<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lattice_reduction" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lattice_reduction</a><p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lenstra–Lenstra�%...</a><p>[2] <a href="https:&#x2F;&#x2F;www.newton.ac.uk&#x2F;files&#x2F;seminar&#x2F;20140509093009501-202978.pdf" rel="nofollow">https:&#x2F;&#x2F;www.newton.ac.uk&#x2F;files&#x2F;seminar&#x2F;20140509093009501-202...</a><p>[3] <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1003.5461.pdf" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;1003.5461.pdf</a><p>[4] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Factorization_of_polynomials#F...</a><p>[5] <a href="https:&#x2F;&#x2F;web.eecs.umich.edu&#x2F;~cpeikert&#x2F;lic13&#x2F;lec05.pdf" rel="nofollow">https:&#x2F;&#x2F;web.eecs.umich.edu&#x2F;~cpeikert&#x2F;lic13&#x2F;lec05.pdf</a><p>[6] <a href="https:&#x2F;&#x2F;github.com&#x2F;fplll&#x2F;fplll" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;fplll&#x2F;fplll</a>