This is really helpful Martin! Thank you very much. I shall have a thorough look at this.
And I would be very happy to contribute too. Regards, Ermis 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
