Analysis of Bernstein's NFS by Arjen Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer

[Anish M]

Hi,
 The analysis of Bernstein's NFS by Arjen  Lenstra, Adi Shamir, Jim
Tomlinson, Eran Tromer  has been put up on cryptosavy.com
seems interesting it comes from  Lenstra and Shamir .Lenstra lead the 1994
factorisation of RSA 129.The abstract ....

Abstract. In [1], Bernstein proposed a circuit-based implementation of
the matrix step of the number field sieve factorization algorithm. We
show that under the non-standard cost function used in [1], these circuits
indeed o
er an asymptotic improvement over other methods but
to a lesser degree than previously claimed: for a given cost, the new
method can factor integers that are 1.17 times larger (rather than 3.01).
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.
We conclude that from a practical standpoint, the security of RSA relies
exclusively on the hardness of the relation collection step of the number
field sieve.

anish
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Anish.vcf
Type: text/x-vcard
Size: 317 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20020604/2fcefe4b/attachment.vcf>