Mersenne: /. article
http://slashdot.org factoring breakthrough? YotN, Henk Stokhorst _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: /. article
That paper sounds like a genuine revolution. I have looked at two papers of Bernstein before, Prime Sieves Using Binary Quadratic Forms together with A.O.L. Atkin (algorithm a.k.a. Sieve of Atkin, implementation by Bernstein available under the name primegen), and How to Find Small Factors of Integers, of which I wrote a simple implementation just recently. Both algorithms perform admirably. Bernstein is certainly not a charlatan. I understand far too little of NFS to get any of the details of the paper, but if Bernstein's ideas should prove to work, it seems that all the experts' past predictions on the difficulty of integer factoring will look rather ridiculous ..again. I'm on the edge of my seat right now. I can't wait for the experts to comment this paper. Alex Henk Stokhorst wrote: http://slashdot.org factoring breakthrough? YotN, Henk Stokhorst _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: /. article
On 26 Feb 2002, at 19:46, Henk Stokhorst wrote: http://slashdot.org factoring breakthrough? Doesn't look like a breakthrough, although there may be a very significant reduction in the amount of work required to factor awkward numbers. The implications in terms of public key cryptography look as though they could be significant - those secure 128-bit cyphers in widespread use for e-commerce are starting to look pretty transparent, but doubling the number of bits in the key is more than sufficient to defeat this latest advance. Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: /. article
[EMAIL PROTECTED] wrote: On 26 Feb 2002, at 19:46, Henk Stokhorst wrote: http://slashdot.org factoring breakthrough? Doesn't look like a breakthrough, although there may be a very significant reduction in the amount of work required to factor awkward numbers. The implications in terms of public key cryptography look as though they could be significant - those secure 128-bit cyphers in widespread use for e-commerce are starting to look pretty transparent, but doubling the number of bits in the key is more than sufficient to defeat this latest advance. The 128 bits refer to the symmetric part of the protocol. Asymmetric ciphers are much slower than symmetric, so in practice one generates a session key for a symmetric cipher, encrypts that asymetrically and sends it to the other guy, and encrypts the actual communication with the symmetric key that both now have. For example, the Web Email service of the LRZ München uses 128 bit RC-4 for the symmetric part, and a 2048-bit RSA key for the asymmetric part, according to Opera. The symmetric ciphers are totally unaffected by advancements in integer factoring, but the asymmetric are not. Many public-key systems rely on the difficulty of factoring integers (i.e. RSA) or of computing discrete logarithms (ElGamal) and the ideas in Bernstein's paper can supposedly speed up both. Bernstein's point is that custom built hardware can reduce the asymptotic complexity of NFS factoring rather than offering just a linear speedup. He claims that with the same hardware cost, custom built hardware can factor numbers in the same time that a general purpose machines needs to factor numbers of a third the size. If that should prove true, it would be well deserving of the word breakthrough. It remains to be seen whether the ideas work with numbers of interesting size (150-300 decimals, say) and whether the proposed circuits can be practically realised. Regards Brian Beesley Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: /. article
Well anything that can increase the speed of TF by even a wee amount is welcome by me. _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: LL test efficiency
For those of you interested in optimizing efficiency of LL testing: We are approaching first time tests of 15.30M exponents, at which point the Prime95 program will start using an 896K FFT. However, the P4-SSE2 section of the program will start using that larger FFT size at 15.16M exponents, making it (relatively) inefficient to test exponents between 15.16M and 15.30M on a P4. Since the Primenet server doesn't take this into consideration when assigning exponents, I would suggest you all have enough exponents queued up on your P4s before the server reaches 15.16M to keep them busy until it reaches 15.30M. I know there are other ways around it, but that is the simplest. Steve Harris _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers