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 'short' 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 "B-smooth". 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'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 "approximately equal to".<p>u is chosen as the product of primes of all a_i > 0 and v is chosen to be the product of all primes where a_i < 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 'weighting' 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've been confused about this for over a decade as variants of this algorithm, and Schnorr's work in general, have been well published. For example, there's a paper from 2010 on "A Note on Integer Factorization Using Lattices" by Antonio Vera which discusses Schnorr'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's factor polynomials also with integer coefficients) [4] and has been used to break other (now very old) cryptosystems [5]. If there's a candidate algorithm to solve integer factoring, lattice reduction (LLL, PSLQ, etc.) are it.<p>I know of fplll that's a stand alone (FOSS) implementation of LLL and some extensions (BKZ, etc.) [6].<p>[0] <a href="https://en.wikipedia.org/wiki/Lattice_reduction" rel="nofollow">https://en.wikipedia.org/wiki/Lattice_reduction</a><p>[1] <a href="https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...</a><p>[2] <a href="https://www.newton.ac.uk/files/seminar/20140509093009501-202978.pdf" rel="nofollow">https://www.newton.ac.uk/files/seminar/20140509093009501-202...</a><p>[3] <a href="https://arxiv.org/pdf/1003.5461.pdf" rel="nofollow">https://arxiv.org/pdf/1003.5461.pdf</a><p>[4] <a href="https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers" rel="nofollow">https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...</a><p>[5] <a href="https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf" rel="nofollow">https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf</a><p>[6] <a href="https://github.com/fplll/fplll" rel="nofollow">https://github.com/fplll/fplll</a>