mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2008-06-13, 06:40   #12
Visu
 
Visu's Avatar
 
Nov 2006
Singapore

7510 Posts
Default

Quote:
Originally Posted by xilman View Post
How about a side bet?

Same conditions except that there's no requirement that the factorization be performed by GNFS but, rather, is a demonstration of an algorithm and its implementation which is capable of factoring a hard 1024-bit (or greater) integer.

The quantum computer people, last time I heard (8 years ago) were also predicting "15-20 years" for kilobit factorizations by Shor's algorithm. We've no idea (at least, I've no idea) whether a new algorithm will turn up in the near future. If it does, or if the QC people hit their target, it may well be possible to perform a kilobit GNFS within ten years but not cost-effective to do so. Compare the situation with 512-bit factorizations. It's undoubtedly possible to do one with QS now but there's no real incentive to prove that claim.


Paul
Seems to me that if you win this bet, you might lose the other one. If there is another even better algorithm, people would be less inclined to use GNFS.
Visu is offline   Reply With Quote
Old 2008-06-13, 08:00   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001000111112 Posts
Default

Quote:
Originally Posted by Visu View Post
Seems to me that if you win this bet, you might lose the other one. If there is another even better algorithm, people would be less inclined to use GNFS.
Think about my possible reason(s) for making the second bet.

Paul
xilman is offline   Reply With Quote
Old 2008-06-13, 08:33   #14
Visu
 
Visu's Avatar
 
Nov 2006
Singapore

3×52 Posts
Default

Quote:
Originally Posted by xilman View Post
Think about my possible reason(s) for making the second bet.

Paul
Well you seem to have increased your chances of not losing by adding the second bet.
Visu is offline   Reply With Quote
Old 2008-08-28, 21:32   #15
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

3×5×7 Posts
Default

At Crypto 2008 was presented an attack against GPcode.

Unsurprisingly, the attack vector was not the RSA modulus, but the weak stream cipher used to encrypt the files (RC4, sigh).
Robert Holmes is offline   Reply With Quote
Old 2008-08-29, 11:49   #16
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1052710 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
The progress has come from two sources: new algorithms and faster/bigger
computers. We have not had a new algorithm in 20 years. Determining how
much more can be squeezed from NFS via faster/bigger computers is
problematic. Note that new algorithms alone have not helped. GNFS
could not have even been run on computers from (say) 1987. They did not
have enough memory.
Bob, you disappoint me. You've a well-deserved reputation for requiring posters to use precise language and then you fall down on this one.

There's no doubt that GNFS could have run on 1987-era machines. Out-of-core sieving and linear algebra could have been done. A gigabyte or few of disk space was relatively cheap even then. At that time the oil companies already had terabyte disk arrays and petabyte tape libaries to hold all their seismological data.

If you had written something like "GNFS would have been very slow" or "GNFS would not have been cost-effective" I'd have no argument.

Paul

Last fiddled with by xilman on 2008-08-29 at 11:49 Reason: Make sure your irony detector has been serviced recently before flaming me.
xilman is offline   Reply With Quote
Old 2008-08-29, 12:32   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
Bob, you disappoint me. You've a well-deserved reputation for requiring posters to use precise language and then you fall down on this one.

There's no doubt that GNFS could have run on 1987-era machines. Out-of-core sieving and linear algebra could have been done. A gigabyte or few of disk space was relatively cheap even then. At that time the oil companies already had terabyte disk arrays and petabyte tape libaries to hold all their seismological data.

If you had written something like "GNFS would have been very slow" or "GNFS would not have been cost-effective" I'd have no argument.

Paul
Please. A new workstation in 1987 was a SUN-3/75 or perhaps a SPARC-1.
It had (fully loaded) 4-8Mbytes (not Gbytes) of memory. The factor base
for even 100-digit SNFS jobs would not have fit in memory. An out-of-core
siever would have been so slow that it would not be worth doing. The
LA would have been even worse. QS would have been faster. And the
largest matrices that we could deal with at that time had only about 80K
rows.
R.D. Silverman is offline   Reply With Quote
Old 2008-08-29, 13:47   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·112·29 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Please. A new workstation in 1987 was a SUN-3/75 or perhaps a SPARC-1.
It had (fully loaded) 4-8Mbytes (not Gbytes) of memory. The factor base
for even 100-digit SNFS jobs would not have fit in memory. An out-of-core
siever would have been so slow that it would not be worth doing. The
LA would have been even worse. QS would have been faster. And the
largest matrices that we could deal with at that time had only about 80K
rows.
I'm not denying any of that, apart from the last (a 1M dense bit-matrix fits into 128G, slow but possible). I'm asking only for precision in language.



Paul
xilman is offline   Reply With Quote
Old 2008-08-29, 19:03   #19
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67168 Posts
Default

Quote:
Originally Posted by Robert Holmes View Post
At Crypto 2008 was presented an attack against GPcode.

Unsurprisingly, the attack vector was not the RSA modulus, but the weak stream cipher used to encrypt the files (RC4, sigh).
This is very cool, but I predict the next gpcode version will use 128-bit AES. Good luck cryptanalyzing that...

It's just another escalation in the malware arms race. Meanwhile the authors continue to get rich.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
It won't stop giving me ECM, help! 137ben PrimeNet 5 2012-03-29 12:43
Sieving: When to stop? SaneMur Riesel Prime Search 4 2011-07-18 17:04
When will it stop? ThomRuley Msieve 20 2010-05-19 02:12
Should we stop at k=249? jocelynl 15k Search 2 2004-07-10 13:31
RMA - stop LLR bug paulunderwood 3*2^n-1 Search 8 2004-05-19 07:10

All times are UTC. The time now is 05:58.

Thu Jan 28 05:58:12 UTC 2021 up 56 days, 2:09, 0 users, load averages: 2.62, 2.55, 2.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.