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
