Factorization of a 768-bit RSA modulus

[jasonp]

Originally Posted by Andi47

I think so too, but how to FIND a sextic polynomial?

The same way you find degree-4 and degree-5; the algorithm is independent of the polynomial degree, even if the code is not :)

While finding degree 6 polynomials is possible now, searching the space for good degree 6 polynomials is turning out to be surprisingly difficult unless the space is forced to be extremely small.

[frmky]

I'm a bit late to the party, but congrats! NFS@Home is honored to have earned a reference in the paper.

[jasonp]

Comment in an Ars Technica thread, on why it's silly to base encryption on prime numbers because you can tabulate them all:

That's basically what they did. Instead of finding and storing all the 
primes they found and stored the products of all the primes. This took 
them 1500 years of processor time and 5TB to store the resulting data, 
so it's not quite as easy as you make it sound.

[bdodson]

Originally Posted by xilman

I've now seen the full paper and will be mailing one of the authors with a suggestion for an amendment. Almost all my sieving was done on the teaching lab machines at the Genetics dept. of Cambridge University and I'd like that to be on record.

Paul

The version currently attached to the above link, version 1.0, includes
this correction. A friendly ammendment, certainly. -BD

[ixfd64]

I wonder if RSA will mention this on its website despite having discontinued the contest in 2007. RSA did announce the factorization of RSA-200 from the old contest that was also cancelled, so I'm pretty curious how this will go.

[10metreh]

Would RSA-1024 need a septic polynomial if it were ever done by GNFS?

[Batalov]

Maybe

[thome]

Originally Posted by 10metreh

if we have a degree 6 poyfinder and a block Wiedemann implementation; is there a chance that any of the software used could become available to the public?

The block wiedemann implementation in cado-nfs exists, with two major blockers though (which depend on the little time I can allocate to it):
- there's no real documentation on how to run it in an mpi environment (but it works -- it's a matter of writing up some doc, and finish writing one matrix preparation tool).
- the central matrix berlekamp-massey code needs to be rewritten entirely in order to handle problems of this size. This is not trivial. The code we used for the factorization is not distributed presently.

A block Lanczos using the mpi+pthreads matrix product from cado-nfs would not be terribly hard to write. Might happen not too far from now.

E.

[thome]

Originally Posted by 10metreh

Would RSA-1024 need a septic polynomial if it were ever done by GNFS?

The asymptotics tell you this (with bc -l):

n=2^768
e(l(3*l(n)/l(l(n)))/3)
6.33644328171517744982
n=2^1024
e(l(3*l(n)/l(l(n)))/3)
6.87076171913041326630

So 1024 nears the 6-7 border. I haven't spent a second of work on the topic, but it seems likely that degree 6 still wins for 1024. Kleinjung's paper at sharc06 suggest a polynomial of degree 6 as well, which is a mild indication that perhaps he also tried 7 and found out that 6 was better. anyway.

E.

[thome]

Originally Posted by bsquared

Fantastic! Cheers to all involved!

The paper mentions that a deliberate decision was made to not BOINCify or otherwise open up the sieving stage of the computation; mostly I gather from the desire to set a reasonably precise completion date and from a data management standpoint. I wonder how much could be gained if they opened it up, assuming the resources (administration/data management) were available? If not BOINC then at least a more widespread invitation to contribute. It seems like there would be lots of interest from the community to contribute to a record factorization, but maybe that's just the euphoria talking.

Anyway, congrats again!

Honestly, we were busy enough gathering data from the limited number of contributors. Much of the sieving effort was done from feb. 2008 to feb. 2009, and very importantly, it worked seamlessly with very little human interaction. If we had opened up the sieving stage to the crowd, I think we would have had a harder time supervising the bookkeeping.

So group efforts at this scale are not necessarily frowned upon, but that's really a management and supervision issue. Much easier to split into a small number of groups, rather than to have 1000+ contributors.

E.

[henryzz]

Originally Posted by thome

Honestly, we were busy enough gathering data from the limited number of contributors. Much of the sieving effort was done from feb. 2008 to feb. 2009, and very importantly, it worked seamlessly with very little human interaction. If we had opened up the sieving stage to the crowd, I think we would have had a harder time supervising the bookkeeping.

So group efforts at this scale are not necessarily frowned upon, but that's really a management and supervision issue. Much easier to split into a small number of groups, rather than to have 1000+ contributors.

E.

If you wanted more help at the cost of one more contributer i am sure you would find a volunteer on mersenneforum willing to organize help from mersenneforum+contacts(i.e. nfs@home etc.).