Thread: CADO
View Single Post
Old 2008-11-05, 18:25   #2
Tribal Bullet
jasonp's Avatar
Oct 2004

353410 Posts

CADO had a lot of people present on a wide range of different topics. For NFS implementations, in no particular order, some of the highlights were:

- Peter Montgomery walked through some of his ideas for the postprocessing for RSA768 (the factorization is underway now and the sieving is pretty far along)

- Thorsten Kleinjung explained a new algorithm for GNFS polynomial selection, that is both much simpler than the current champion and promises to find noticeably better polynomials. He quoted 15-23% improved quality over the polynomials produced by his earlier method for RSA512 and RSA640. This was actually my favorite talk of the Workshop, and I'm hard at work implementing the new algorithm for msieve

- Alex Kruppa went through a long list of changes that are necessary for a lattice siever to find more than two large primes in relations, combined with building a network of factoring strategies that include P+-1 and ECM with parameters optimized for small inputs. Currently the CADO lattice siever finds relations with three large primes 25% faster than with two large primes

- Patrick Stach walked through a lot of the low-level details of the linear algebra and talked about mapping the computation onto graphics cards; there are 5x speedups possible for matrix multiplication given more sophisticated hardware knowledge

- Dan Bernstein rolled together a lot of his NFS work into a collection of methods to estimate the runtime of a factorization before starting it; maybe someone can combine these with Willemien Ekkelkamp's method of estimating the runtime given some trial sieving

- I talked about many of the filtering tweaks in msieve; hopefully it provided ammunition for the CADO filtering code

There are no proceedings from the workshop, only the slides (available online).
jasonp is offline   Reply With Quote