fplll
EUL
| fplll | EUL | |
|---|---|---|
| 2 | 1 | |
| 292 | 6 | |
| 1.4% | - | |
| 5.4 | 3.1 | |
| about 1 month ago | 11 months ago | |
| C++ | C++ | |
| GNU Lesser General Public License v3.0 only | GNU General Public License v3.0 only |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
fplll
-
Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”
It's using the FPLLL lattice reduction library.
-
Did Schnorr destroy RSA? Show me the factors
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
EUL
What are some alternatives?
GLM - OpenGL Mathematics (GLM)
Fermat - A library providing math and statistics operations for numbers of arbitrary size.
root - The official repository for ROOT: analyzing, storing and visualizing big data, scientifically
nim-stint - Stack-based arbitrary-precision integers - Fast and portable with natural syntax for resource-restricted devices.
SchnorrGate - Testing Schnorr's factorization claim in Sage
Algorithms - A collection of data structures and algorithms written in C++ with comments and links to further reading.
casadi - CasADi is a symbolic framework for numeric optimization implementing automatic differentiation in forward and reverse modes on sparse matrix-valued computational graphs. It supports self-contained C-code generation and interfaces state-of-the-art codes such as SUNDIALS, IPOPT etc. It can be used from C++, Python or Matlab/Octave.
Seperating-kids-from-fighting-in-group-size-N - This function lists the permutations in which from the first arrangement, no student fights the same pair of students twice