Hi Bill, I will have a look at this p^2+p+1 algorithm. I haven't tried flint to be honest. This might be an alternative solution. Thank you very much!
Regards, Ermis On Jan 29, 9:55 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > 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
