View Single Post
Old 2005-01-27, 21:15   #4
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by akruppa
I once mentioned the same idea to Peter Montgomery, he replied that a certain Bob Silverman mentioned it almost ten years earlier. He also told me that this idea is not implemented in the CWI siever, however multiple polynomial NFS for factoring one number is. Maybe the code could be adapted to the many-numbers-at-once idea.

He also mentioned another nice trick to use symmetry in the algebraic polynomial: for even polynomials, F(a,b) is smooth iff F(-a,b) is, so the algebraic side only needs to sieve nonnegative values. For symmetric polynomials (same coefficients left-to-right as right-to-left), F(a,b) is smooth iff F(b,a) is, though this symmetry seems harder to exploit. He said these tricks are not implemented in the CWI siever, either.



I was aware of the symmetry tricks as well; I had even suggested one or
two to Peter some time ago.

I looked into implementing one of the simpler ones (you discussed it above)
and concluded that you needed too much memory and saving of state
information to be effective.

R.D. Silverman is offline   Reply With Quote