A next big thing - Page 2

Dubslow · 2012-07-23, 18:11

Quote:

Originally Posted by xilman

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?

xilman · 2012-07-23, 18:26

Quote:

Originally Posted by Dubslow

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

Dubslow · 2012-07-23, 18:34

Quote:

Originally Posted by xilman

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

)

retina · 2012-07-23, 18:48

Quote:

Originally Posted by Dubslow

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.

Xyzzy · 2012-07-23, 18:58

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

henryzz · 2012-07-23, 21:47

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.

xilman · 2012-07-24, 09:38

Quote:

Originally Posted by henryzz

@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.

c10ck3r · 2012-07-24, 15:28

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?

retina · 2012-07-24, 16:01

Quote:

Originally Posted by c10ck3r

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

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.

bsquared · 2012-07-24, 16:18

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.

jasonp · 2012-07-24, 16:29

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?

2012-07-24, 16:18	#21
bsquared "Ben" Feb 2007 2²×3×311 Posts	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

2012-07-24, 16:29	#22
jasonp Tribal Bullet Oct 2004 110111100011₂ Posts	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

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

2012-07-23, 18:58	#16
Xyzzy Aug 2002 2×7×13×47 Posts	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.)

2012-07-23, 21:47	#17
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 37·163 Posts	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.

2012-07-24, 15:28	#19
c10ck3r Aug 2010 Kansas 547 Posts	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?