Hi all, Since I have the same issue could someone provide the solution? The link to the sage documentation is about small_roots, which only applies for univariate polynomials. However, to find the factorization of RSA given the LSB of the primes requires polynomials on two variables according to Coppersmith's original paper, so this doesn't work. Am I missing something?
Regards, C. On Monday, January 30, 2012 9:56:09 PM UTC, Ermis wrote: > 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 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
