CADO

R.D. Silverman · 2008-11-05, 16:58

Hi,

Would anyone who attended the CADO workshop care to
summarize what went on? Were there any revelations/
insights/new ideas ??

I now have a proof that using a constant area sieve region
for the lattice sieve is not optimal. One should use a larger
region for the smaller special q's and gradually decrease the size
of the region as q increases. However, the speedup obtained does
not seem to be large for a practical reason.

Owing to the way computers address 2D arrays, it is
advantageous to have a sieve region be 2^n x 2^m.
An attempt to use (say) a sieve region that is 1.537 x 2^n
by 3.682 x 2^m would slow down the addressing.....
Thus, while the total number of sieve points would be reduced
by following an optimal "size strategy", addressing those points
would be slower.

I can write this up and submit a paper, but since the optimization
is not (very) effective, I am not sure that it is worth doing.

jasonp · 2008-11-05, 18:25

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

Batalov · 2008-11-05, 18:52

http://cado.gforge.inria.fr/workshop/ Fantastic slides.
http://cado.gforge.inria.fr/software.en.html Sadly, not yet.

R.D. Silverman · 2008-11-05, 19:29

Quote:

Originally Posted by jasonp

- 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
There are no proceedings from the workshop, only the slides (available online).

Didn't Alex give any consideration to splitting the cofactors with QS?
I have found that it is faster than the alternatives.....

akruppa · 2008-11-06, 12:35

I found that with two 30-bit primes (so that the product fits in one word), ECM is almost as fast as Kleinjung's MPQS. Often one prime is a smaller than the other, which gives ECM an advantage. If their product is a little bigger than the word size, MPQS should have a noticeable advantage. If the composite needs to have 3 factors to be smooth, ECM with an early abort strategy will perform far better than MPQS which doesn't tell anything about likely smoothness until it found the actual factors. All in all, an implementation with only P-1, P+1 and ECM can perform quite well, although for some particular cases it would be worthwhile to have MPQS around as a fall-back.

Alex

2008-11-05, 16:58	#1
R.D. Silverman "Bob Silverman" Nov 2003 North of Boston 2·3³·139 Posts	CADO Hi, Would anyone who attended the CADO workshop care to summarize what went on? Were there any revelations/ insights/new ideas ?? I now have a proof that using a constant area sieve region for the lattice sieve is not optimal. One should use a larger region for the smaller special q's and gradually decrease the size of the region as q increases. However, the speedup obtained does not seem to be large for a practical reason. Owing to the way computers address 2D arrays, it is advantageous to have a sieve region be 2^n x 2^m. An attempt to use (say) a sieve region that is 1.537 x 2^n by 3.682 x 2^m would slow down the addressing..... Thus, while the total number of sieve points would be reduced by following an optimal "size strategy", addressing those points would be slower. I can write this up and submit a paper, but since the optimization is not (very) effective, I am not sure that it is worth doing.

2008-11-05, 18:52	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10011101000001₂ Posts	http://cado.gforge.inria.fr/workshop/ Fantastic slides. http://cado.gforge.inria.fr/software.en.html Sadly, not yet. Last fiddled with by Batalov on 2008-11-05 at 19:02 Reason: (links "for the rest of us"; I know that you know)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
CADO help	henryzz	CADO-NFS	6	2022-09-13 23:11
CADO-NFS on windows	jux	CADO-NFS	25	2021-07-13 23:53
CADO NFS	Shaopu Lin	CADO-NFS	522	2021-05-04 18:28
CADO and WinBlows	akruppa	Programming	22	2015-12-31 08:37
CADO-NFS	skan	Information & Answers	1	2013-10-22 07:00

2008-11-05, 18:25	#2
jasonp Tribal Bullet Oct 2004 3²·5·79 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).

2008-11-06, 12:35	#5
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I found that with two 30-bit primes (so that the product fits in one word), ECM is almost as fast as Kleinjung's MPQS. Often one prime is a smaller than the other, which gives ECM an advantage. If their product is a little bigger than the word size, MPQS should have a noticeable advantage. If the composite needs to have 3 factors to be smooth, ECM with an early abort strategy will perform far better than MPQS which doesn't tell anything about likely smoothness until it found the actual factors. All in all, an implementation with only P-1, P+1 and ECM can perform quite well, although for some particular cases it would be worthwhile to have MPQS around as a fall-back. Alex