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

11100001101012 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

2×5,477 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×29×83 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

11×571 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
 
Aug 2002

100000011101102 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)

3·1,973 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 online now   Reply With Quote
Old 2012-07-24, 09:38   #18
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2ACA16 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

22316 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

11·571 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·1,789 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

DD716 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 21:18.


Wed Oct 20 21:18:35 UTC 2021 up 89 days, 15:47, 1 user, load averages: 1.23, 1.39, 1.35

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.