RSA-640

[akruppa]

Finding polynomials is easy. It is trivially parallelizable and can be split between as many machines as desirable.

Is degree 5 still optimal for 640 bits? If, say, Kleinjung's program has to be adapted for degree 6 first, searching polynomials may turn out to be a distinctly non-trivial task.

Alex

[scottsaxman]

There are a number of people paddling furiously underneath the NFSNET you see on the surface.

Hats off to all you furious paddlers out there! I was shamelessly unaware of the size of operations. Good to know someone out there is keeping track, though.

Again, thank you for your diligent efforts.

[xilman]

Originally Posted by akruppa

Is degree 5 still optimal for 640 bits? If, say, Kleinjung's program has to be adapted for degree 6 first, searching polynomials may turn out to be a distinctly non-trivial task.

Alex

See the Asiacrypt 2003 paper by Lenstra et al (I'm a rather minor al in that one) where polynomial quality is one of the topics investigated as part of an examination of the difficulty of a 1024-bit GNFS factorization. We searched for polynomials of degree 5 through 10, for integers of 512, 768 and 1024 bits. Kleinjung's program crashed when searching for quintics --- the numbers were just too large for it

An alternative polynomial finder, whose authors include Peter Montgomery, Arjen Lenstra and, to an extremely tiny extent, myself worked well enough. It is trivially parallelizable and even though it may be a hundred times slower than Kleinjung's it works for all reasonable degrees. We've heard on apparently good authority here that it would be straightforward to get hundreds of machines working on the problem...

Paul

[xilman]

Originally Posted by Minty

winner. The only potential problem I can see is handing over shedloads of work to a company environment that might be more financially motivated than honesty driven, and that might then go on to submit the factors and claim the entire prize for themselves!

My experience is quite the reverse. Companies frequently have no mechanism for dealing with such sporadic and small amount of money raised by such means. It confuses the hell out of the bean counters.

At Microsoft Research any prize money of that form was funnelled straight through to an appropriate charity without it touching the company in any significant manner. The beneficiaries were Cancer Research Campaign (now called Cancer Research UK) for RSA-140, the Bletchley Park Trust for RSA-512 and the Lance Armstrong Foundation (an Austin Tx based cancer charity) for my portion of NFSNET's work on RSA-576.

Paul

[Minty]

Thanks for all the info - it's very much appreciated and interesting to hear about the work behind the scenes.
If we stand back from NFSNet and take a look, we see that it's amazing that it's actually still going. It seems that it's on the verge of being viable and not because of the human input necessary.
To return to a previous point though, I was wondering how much more human work it would be to run an RSA than normal factors over the same period - I say this because if NFSNet is going to bust a gut processing relatively unknown numbers, would it not be better to attempt something with a potential of financial gain (for just a bit gut more) that could be ploughed back into the project to perhaps i.e. fund new siever software/another server etc.? The concept of giving prize money to charity is morally noble, but in this context of deprivation could NFSNet not be its own charity?! Although the amounts of money might not be enough, maybe they could act as incentives for someone to help out (with the siever etc.) Without some boost NFSNet will probably die, especially as it has lost access to the useful Microsoft facilities, and those working hard at the top are bound to be getting weary by now - bleeuuhh.

[ColdFury]

Some people have succeeded if, by "distributed computing platform", you mean two or more self-contained computers connected together by a network. Peter Montgomery's implementation works very well in such an environment and it was used for all the NFSNET matrices until I left Microsoft Research.

I think he meant large-scale internet distributed computing, similar to D.net or Prime95. There's just too much communication required between nodes.

[xilman]

Originally Posted by Minty

To return to a previous point though, I was wondering how much more human work it would be to run an RSA than normal factors over the same period

Almost the same. The only difference between SNFS (which is what we've been doing so far) and GNFS (needed to factor an RSA challenge number) is findng the polynomials. With SNFS there is usually one polynomial which is self-evidently the best. Even where there's a choice, deciding between them is a matter of a few minutes typing and a few hours computation on a single machine. With GNFS we have to search for polynomials and then evaluate the quality of the top-rated candidates. It is more human work, but not a lot more work. Takes more elapsed time and cpu time, though, because of the need to search a fairly wide parameter space.

Originally Posted by Minty

- I say this because if NFSNet is going to bust a gut processing relatively unknown numbers, would it not be better to attempt something with a potential of financial gain (for just a bit gut more) that could be ploughed back into the project to perhaps i.e. fund new siever software/another server etc.? The concept of giving prize money to charity is morally noble, but in this context of deprivation could NFSNet not be its own charity?! Although the amounts of money might not be enough, maybe they could act as incentives for someone to help out (with the siever etc.)

Who and/or what is NFSNET? Who would the check be made to? What happens to the money after that? I forget the exact prize money on offer, but it's probably in the region of $20K. If NFSNET is the people who made contributions, the software authors (which includes CWI who wrote virtually all the number theoretical code) and the people who ran the clients and servers would all be entitled to a contribution. You know, or can easily find out, the rough size of that number. You can do the division. You can work out how much each is likely to get. You can also work out how much would be lost in bank charges, currency conversion and postage. Someone also has to coordinate all that activity.

If you go through the exercise outlined above, perhaps you will see why it's rather common practice just to say hang it all, we'll give anything we win to charity as a lump sum, or to avoid challenges with prize money attached.

Originally Posted by Minty

Without some boost NFSNet will probably die, especially as it has lost access to the useful Microsoft facilities, and those working hard at the top are bound to be getting weary by now - bleeuuhh.

Yes, it can be wearying at times. There is a lot of work and, because the clients are running 24/7, it can seem relentless. By far the best boost we could get is more skilled labour. Serious offers only, please.

Paul

[Mystwalker]

Originally Posted by xilman

Who and/or what is NFSNET? Who would the check be made to? What happens to the money after that? I forget the exact prize money on offer, but it's probably in the region of $20K. If NFSNET is the people who made contributions, the software authors (which includes CWI who wrote virtually all the number theoretical code) and the people who ran the clients and servers would all be entitled to a contribution. You know, or can easily find out, the rough size of that number. You can do the division. You can work out how much each is likely to get. You can also work out how much would be lost in bank charges, currency conversion and postage. Someone also has to coordinate all that activity.

Well, I think something like http://www.mersenne.org/prize.htm is completely ok. Of course, there is no person whose client finds a prime. When you take that away (right now, people already donate their CPU time voluntarily), You maybe get:

50% for server housing (+ maintenance), bandwidth and so on
10% for CWI
20% for administrators donating (not few of) their very time for the project
20% for major contribution - if there are none, increase the other sums according to their percentage

I don't think any volunteer minds continuing the work. It would be nice to be mentioned in the press release, though (for those that desire it)...

P.S.: This thread is already on position #5 on Google when searching for "RSA-640".

[Minty]

Originally Posted by xilman

Who and/or what is NFSNET? Who would the check be made to? What happens to the money after that? I forget the exact prize money on offer, but it's probably in the region of $20K. If NFSNET is the people who made contributions, the software authors (which includes CWI who wrote virtually all the number theoretical code) and the people who ran the clients and servers would all be entitled to a contribution. You know, or can easily find out, the rough size of that number. You can do the division. You can work out how much each is likely to get. You can also work out how much would be lost in bank charges, currency conversion and postage. Someone also has to coordinate all that activity.

I hear where you're coming from - you have the skill and experience and are therefore in an excellent position to help guide the project along the best path . From my point of view, it seems that there is far too much manual labour involved in the factoring process - the computer after all should be a labour saving tool and not an unforgiving 24/7 sleepless master!
As far as prize money goes, I don't think anyone should benefit in particular if they are happy working as they are. My take on the situation is as follows:
There is a serious problem with high manual workload threatening the project. The solution seems to be new fully automated upgraded robust client/server software (with error checking etc.) that is up to the job. Perhaps CWI might be capable/interested in undertaking this - I have no idea whether $15,000 would be anything like enough, but I'll assume it is for now. Proceed as follows:
1)Ensure everyone at the top of NFSNet is happy with the plan below (if not abort),
2)Check to see if Franke/others might already be working on RSA-640 (if so abort)
3)If not, negotiate prize money just for solving the RSA-640 matrix,
4)Solve RSA-640 (!) - pay Paul $20,000 (if willing to accept! or someone in the US to avoid multiple currency conversions)
5)Contract software development company to undertake rewrite - presumably CWI are already experienced in such matters. Liaise to iron out problems, and test.
6)If any money is left over, spend on server for NFSNet, or donate to charity.
7)Let the machines do most of the work in the future - maybe even attempt RSA-704!!!

I know this is very brief and most probably flawed, but it might at least get people thinking of the future of NFSNet. If any of this is remotely possible, then I hereby call on NFSNet to mount an attack on RSA-640!

Originally Posted by Mystwalker

P.S.: This thread is already on position #5 on Google when searching for "RSA-640".

Wow! Thanks for pointing that one out - I hadn't even thought about it - and it seems to be up to 3rd now!

[xilman]

Originally Posted by Minty

I hear where you're coming from - you have the skill and experience and are therefore in an excellent position to help guide the project along the best path . From my point of view, it seems that there is far too much manual labour involved in the factoring process - the computer after all should be a labour saving tool and not an unforgiving 24/7 sleepless master!

Agreed.

Originally Posted by Minty

There is a serious problem with high manual workload threatening the project. The solution seems to be new fully automated upgraded robust client/server software (with error checking etc.) that is up to the job.
...
Contract software development company to undertake rewrite - presumably CWI are already experienced in such matters. Liaise to iron out problems, and test.

CWI are very unlikely to want to take on this task, IMO. I could be wrong but I know the people at CWI interested in NFS quite well. There are two of them, most of the time --- Herman te Riele and Peter Montgomery. Peter divides his time between CWI and MS Research in Redmond. Herman often has a grad student or post-doc working with him; I've known some of them quite well too. All in all, I don''t think anyone at CWI will want to rewrite NFSNET.

Earlier I wrote:

Originally Posted by xilman

. By far the best boost we could get is more skilled labour. Serious offers only, please.

That was meant to be taken seriously. I really do not believe that there is any chance whatsoever of paying for such help in any currency other than kudos.

Paul

[Mystwalker]

Originally Posted by xilman

CWI are very unlikely to want to take on this task, IMO.
[...]
Herman often has a grad student or post-doc working with him; I've known some of them quite well too. All in all, I don't think anyone at CWI will want to rewrite NFSNET.

Maybe the RSA prize money can be used to hire some student(s) to do this job. Currently, I work for ~10€/hr, assuming a similar pay means ~1,250 manhours, which likely improves NFSNET a lot.

Just to make sure:
I only post suggestions, unable to know whether it could work or not. Call this all a brain storming, ok?

Earlier I wrote: "By far the best boost we could get is more skilled labour. Serious offers only, please."
That was meant to be taken seriously. I really do not believe that there is any chance whatsoever of paying for such help in any currency other than kudos.

When I first read this, I thought "I don't think my skills fit. " - but then it came to my mind I don't even know what skills you need...