There's an LLL in flint 1.5, called ULLL which is very fast for large lattice entries. It is probably subquadratic with respect to bit size of the entries though likely not quasilinear. (We also have a highly hacked version of fpLLL in flint specifically set up for knapsack lattices.)
I recently bumped into an algorithm for factoring with known bits, called the p^2+p+1 algorithm. It has a generalisation to other cyclotomic polynomials. I think there are still some open questions there, but I don't recall LLL being used in that algorithm, so I guess this may not be of interest to you. Bill. On Jan 29, 8:41 pm, Martin Albrecht <martinralbre...@googlemail.com> wrote: > On Sunday 29 January 2012, Ermis wrote: > > > Hi all, > > Hi, > > > I am focusing on the LLL algorithm for my PhD. > > Specifically, on its application on Factorising RSA modulus N with > > high or low-order bits (of the prime p) known. > > My scope is to use an implementation and run tests on the > > factorisation problem. > > > SAGE has embedded Stehle's LLL version: the fplll. > > But, I have not found any module on SAGE for factorising an RSA > > modulus with high or low-order bits known (there is a module called > > SmallRoots on MAGMA, but it is not practical). > > We have small roots as well: > > sage: F = Zmod(3*7) > sage: F > Ring of integers modulo 21 > sage: P.<x> = F[] > sage: type(x) > <type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'> > sage: x.small_roots? > > See "sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots()" > for the documentation of this function. > > EXAMPLE: > > sage: N = 10001 > sage: K = Zmod(10001) > sage: P.<x> = PolynomialRing(K) > sage: f = x^3 + 10*x^2 + 5000*x - 222 > sage: f.small_roots() > [4] > > Furthermore, > > sage: sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots? > > even gives RSA factoring with known bits as an explicit example. > > > So - given that SAGE contains a lot of related modules in this area - > > my question is whether there is plan to create such a module in SAGE, > > or if there is some alternative solution for the RSA factorisation > > problem > > > Thank you. > > Actually, since you're doing a PhD about LLL: the version of fpLLL we ship > with Sage is very old and it would be a great service to the community to > update it to the most recent upstream release which 4.0: > > http://perso.ens-lyon.fr/xavier.pujol/fplll/ > > This version also has an implementation of BKZ which likely is faster than > what we wrap of NTL. Having that readily available in Sage would be awesome! > > Cheers, > Martin > > -- > name: Martin Albrecht > _pgp:http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF > _www:http://martinralbrecht.wordpress.com/ > _jab: martinralbre...@jabber.ccc.de -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
