Slashdot Mirror

← Back to Stories (view on slashdot.org)

Bernstein's NFS analyzed by Lenstra and Shamir

Posted by CmdrTaco on from the my-c0de-is-s3kr37 dept.

kousik writes "The analysis of Bernstein's NFS by Arjen Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer has been put up on cryptosavvy. Seems interesting it comes from Lenstra and Shamir. Lenstra lead the 1994 factorisation of RSA 129. From the abstract: ... We also propose an improved circuit design based on a new mesh routing algorithm, and show that for factorization of 1024-bit integers the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars..."

2 of 168 comments (clear)

  1. errrrr NFS? by karrde · · Score: 5, Informative

    Let's just ignore the fact that we're all a bunch of geeks, and the acronymn NFS usually equal 'Network File System'. Not 'Number Field Sieve' as it does in this case. Would it have been so dificult to say that in the post?? The first link doesn't even give you that information.

  2. Re:Quotes from the paper by Telastyn · · Score: 3, Informative

    Furthermore the paper goes on to say that the major improvements were done to the matrix half of the procedure rather than the collection side. "Half" probably isn't the most accurate term, as the collection side takes far longer (months) than the matrix side (days).

    Even if you remove the matrix side, it takes a VERY long time to find all of the relations needed to make the matrix in order to solve it.