SchnorrGate VS fplll

They use Schnorr’s algorithm for factoring, which is very different from Shor’s algorithm that you might have heard of. It is not clear that is actually scales to larger numbers like the authors propose here. There is evidence that it requires much larger lattices than they claim. Still something to investigate further, but not an immediate worry I think.

Here's an implementation of Schnorr's algorithm with an attempt to estimate the amount of work needed to factorize big numbers: https://github.com/lducas/SchnorrGate

It also contains some links to critique of the Schnorr's algorithm paper. It looks like either much more p_n-smooth integer pairs are needed or the size of the p_n-smooth integers should be much bigger than estimated by original Schnorr's paper. Or both estimations are off.

As the paper discussed Schneier relies on the assumptions of the (classic) Schnorr's algorithm, it may also be off in the calculations as well.

https://github.com/lducas/SchnorrGate is an analysis from someone that attempted to implement the code in the paper. It sounds like there are some "sensible" ideas in the paper, but that it doesn't hold up as well as claimed.

Leo Ducas has a sage implementation of the algorithm here. You may also be interested in this crypto SE thread discussing the method.

Someone implemented it and it seems worst than what actually exists: https://github.com/lducas/SchnorrGate

SchnorrGate

It's using the FPLLL lattice reduction library.

where ~= means "approximately equal to".

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.

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.

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.

Is Schnorr trying to shout louder so people will listen or is there something else fundamentally flawed with this type of algorithm?

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.

I know of fplll that's a stand alone (FOSS) implementation of LLL and some extensions (BKZ, etc.) [6].

[0] https://en.wikipedia.org/wiki/Lattice_reduction

[1] https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...

[2] https://www.newton.ac.uk/files/seminar/20140509093009501-202...

[3] https://arxiv.org/pdf/1003.5461.pdf

[4] https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...

[5] https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf

[6] https://github.com/fplll/fplll