View Single Post
Old 2007-02-23, 22:07   #1
bsquared's Avatar
Feb 2007

25×113 Posts
Default poly selection in MPQS

I've written a version of MPQS in C and was hoping to get some confirmation of my thoughts on one specific issue with the polynomial selection so that I can finally stop debugging it...

I want to choose the polynomial 'a' value as close as possible to sqrt(2*N)/M, where M is the size of the sieve interval, so that the poly values are as small as possible. Furthermore, 'a' = d^2, where d is a prime with certain properties. This much I think is common knowledge and is in several papers.

In my first version, every time a new polynomial was generated I just incremented d to the next one that met the criteria, so d and thus 'a' gets increasingly far away from optimal.

To try to fix this, i instead alternate between incrementing and decrementing d so that poly 'a' values are closer to optimal on average. I've verified that the largest 'a' values generated are about half as far from optimal compared to the old version. In other words, if in version 1 a_last - a_opt = X, then in version 2 a_last - a_opt = X/2. where a_last is the last and biggest 'a' value generated.

The problem is this really doesn't seem to make much difference to the speed of the sieve. The number of polynomials needed to complete a factorization is slightly smaller, and the total time spent sieveing is also, but it is hardly noticable.

When I thought about it more, this seems to make sense because even though I now have X/2 instead of X for the largest error from optimal, X itself is tiny compared to 'a'. So half of a tiny number is still tiny, and not much is gained.

In SIQS, i understand that choosing optimal 'a' values is a bit harder, but in mpqs it doesn't matter much.

Does this make sense? Am I missing an even better way to generate 'a' values?

bsquared is offline   Reply With Quote