mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Kibibit

Reply
 
Thread Tools
Old 2012-07-23, 18:11   #12
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160358 Posts
Default

Quote:
Originally Posted by xilman View Post
RSA has passed its use-by date. There are better alternatives readily available. Unfortunately, there is also an immense retro-fitting exercise to carry out.
All the more reason to do it! Make as many people anxious/scared/worried/pissed off as possible! (The rush of power is going to my head... )

How much memory would be needed for sieving? Could GGNFS handle it?
Dubslow is offline   Reply With Quote
Old 2012-07-23, 18:26   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

236158 Posts
Default

Quote:
Originally Posted by Dubslow View Post
How much memory would be needed for sieving? Could GGNFS handle it?
Well, it wouldn't be easy. RDS has expressed the opinion that very few extant machines have enough memory to perform the sieving. His record of predictions has been rather patchs in the past...

The real bottleneck, IMAO, would be twofold. The linear algebra and the project management. I can help with the latter, having had some experience in that area, but not with the former. Solving a matrix which could well be 1G square is not entirely trivial. It's approaching the level of interesting, at least, and possibly challenging on the scale of these things.

A concrete start could be made by looking for sextic polynomials. A few cpu-millennia should suffice --- enough to be accessible right now but, again, not entirely trivial.


Paul
xilman is offline   Reply With Quote
Old 2012-07-23, 18:34   #14
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by xilman View Post
A concrete start could be made by looking for sextic polynomials. A few cpu-millennia should suffice --- enough to be accessible right now but, again, not entirely trivial.
Instead of a "Team Sieve" we could do a "Team Poly Search"

Could you/others coordinate that here?

As for LinAlg, there's clusters more powerful than what frmky's got... (but getting time on them... oh boy )

Last fiddled with by Dubslow on 2012-07-23 at 18:35 Reason: ()
Dubslow is offline   Reply With Quote
Old 2012-07-23, 18:48   #15
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10110101110002 Posts
Default

Quote:
Originally Posted by Dubslow View Post
How much memory would be needed for sieving? Could GGNFS handle it?
Just invent a new algorithm. The NFS type algorithms are starting to show their age and inadequacies now so we are due for a new, fresh and updated version. Come on guys, get to it, get your finger out and starting inventing.
retina is online now   Reply With Quote
Old 2012-07-23, 18:58   #16
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×3,853 Posts
Default

Well, let's do it as a forum, and learn a lot of new things!

http://www.mersenneforum.org/forumdisplay.php?f=97

(Help us think of a snappy/witty/clever forum name.)
Xyzzy is offline   Reply With Quote
Old 2012-07-23, 21:47   #17
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22·1,433 Posts
Default

I am not certain that starting poly selection on RSA1024 now would really help it being finally factored. The poly selection routines in msieve have improved massively in the last couple of years. If we aren't realistically going to be able to do the sieving for a while it might be worth waiting. A better poly can make a huge difference. Considering kilobit gnfs when kilobit snfs stretched us seems silly to me.

@xilman Why is RSA dated? 1024-bit obviously is but people could encode in 4096-bit for example. I suppose other methods are possibly more efficient why providing the extra protection.
henryzz is offline   Reply With Quote
Old 2012-07-24, 09:38   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

34×53 Posts
Default

Quote:
Originally Posted by henryzz View Post
@xilman Why is RSA dated? 1024-bit obviously is but people could encode in 4096-bit for example. I suppose other methods are possibly more efficient why providing the extra protection.
That is exactly the reason.
xilman is offline   Reply With Quote
Old 2012-07-24, 15:28   #19
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

10001000112 Posts
Default

Stupid q? Would it be possible to, instead of using a poly and a NFS (g,s, or otherwise), simply divide it into a number of ranges to TF downwards from the sqrt of RSA-1024? Since the factors are roughly the same size, would this save enough time to make it feasible?
c10ck3r is offline   Reply With Quote
Old 2012-07-24, 16:01   #20
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10110101110002 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
Stupid q? Would it be possible to, instead of using a poly and a NFS (g,s, or otherwise), simply divide it into a number of ranges to TF downwards from the sqrt of RSA-1024?
Yes, it is possible.
Quote:
Originally Posted by c10ck3r View Post
Since the factors are roughly the same size, would this save enough time to make it feasible?
No, this would not likely yield any time savings unless you are stupendously lucky and happen to stumble onto the smaller factor. And by "stupendously lucky" I mean: utterly incredibly amazingly mindblowingly unbelievably stunningly lucky.
Or in other words: Forget it.
retina is online now   Reply With Quote
Old 2012-07-24, 16:18   #21
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·17·97 Posts
Default

It's fun to put numbers to how lucky you'd have to be.

Say your computer can do one trial division in 100 nanoseconds. Then in one day you can test 864 billion 512 bit numbers for divisibility into rsa1024. If you ran 100 billion such computers for 100 billion days you'd be able to test 8.64e33 different 512 bit primes. But there are approximately 2^512 / log(2^512) = 3.78e151 different 512 bit primes. So after doing all that work you'd still only have 1 chance in never of finding the factor.

Last fiddled with by bsquared on 2012-07-24 at 16:18
bsquared is offline   Reply With Quote
Old 2012-07-24, 16:29   #22
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

There is power in accepting that the only way to do something is very difficult. Do that and you're already better off than all the others who don't want to accept the truth.

The odds of guessing the right factors are enormously smaller than the odds of teleporting to Mars due to quantum effects. So did you wear your spacesuit this morning? Winning the lottery is unlikely and people win all the time. Would you buy a Powerball ticket that would only pay out if you guessed all of the next 30 Powerball outcomes correctly?

Last fiddled with by jasonp on 2012-07-24 at 16:32
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ecm thing 3.14159 Miscellaneous Math 3 2016-12-16 23:58
my thing firejuggler Aliquot Sequences 1 2010-05-31 06:57
Very strange thing nngs Software 4 2007-04-14 22:08
Hm... strange thing... Yxine Factoring 1 2006-08-10 13:48
Can not be a good thing :( SB2 3*2^n-1 Search 7 2004-09-23 08:48

All times are UTC. The time now is 01:45.

Tue Oct 27 01:45:43 UTC 2020 up 46 days, 22:56, 0 users, load averages: 1.87, 1.76, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.