RSA-640

[frmky]

Originally Posted by frmky

Interestingly, GGNFS has no user-adjustable parameters for filtering. The only thing that can be changed is the excess number of relations found in the sieving step so that heavier relations can be thrown away in filtering.

I spoke too soon. A new unstable version was released today that includes a new knob to tweak the filtering...

[Jeff Gilchrist]

I guess this question has now been answered if RSA-640 is feasible:
http://www.mersenneforum.org/showthread.php?t=4085

All you need is 80 Opteron boxes in a gigabit cluster and you are all set.

[rdotson]

Originally Posted by Minty

... My main reason for asking is a serious case of crypto-crack withdrawal and I can't think of anything better than to get going again!...

How about something completely different? A different approach to factoring RSA-640 I mean?

A couple of years ago, just to satisfy my curiosity I wrote a Maple program that generated the boolean equations for a symbolic 320 bit by 320 bit polynomial multiplication and then equated the "columns" of the intermediate results (inner product terms?) with bit positions of the RSA-640 number so that the result was 640 equations in 636 unknowns (since 2^0=1 and 2^319=1 of each factor). Then I wrote a program to expand those 130 megabytes of ASCII text equations to remove parenthesis and convert from CNF to DNF. I spent the next six months or so optimizing that program. At the end of the six months I had increased the speed of my program until it was blazingly fast compared to what I had started with, but I had only managed to increase it's capability from expanding (as I recall) the first 22 equations up to expanding the first 27 (or so) of the total 640 equations even though the program's speed had been increased at least a hundred-fold. When I had made the final "tweak" to my program and knew that I could make it no faster, I had a sort of epiphany and came to a much closer understanding of the limits of computability, and in particular the true meaning of the phrase "... in some cases conversion from CNF to DNF can lead to an exponential explosion of the formula."

In any case, I have 130 megabytes of ASCII text equations consisting of 640 equations in 636 unknowns that would yield the solution to the RSA-640 challenge if solved. If you would like to give it a try I'd be happy to provide you with a copy of the equations.

-- Ron