poly selection in MPQS

[bsquared]

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?

Thanks,
ben.

[jasonp]

Originally Posted by bsquared

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.

As you conclude above, this is pretty much expected. With the A values being the square of a prime that is incremented, you will be very close to optimal essentially permanently (of course if the number to be factored is very small, you'll walk away from the optimal A value quickly, and there isn't much you can do about that; but for such numbers you need very few polynomials).

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

The analogous procedure in SIQS is to use a sieve to choose the primes making up a given A value, but as the number to be factored increases in size the sieve becomes increasingly inefficient, especially if you want to find A values that have a predetermined number of factors. Other authors fix the number of primes making up A and then use a dictionary enumeration algorithm to go through all the combinations of candidate primes (google for 'NEXKSB', this algorithm is very cool), but this is hard to implement when several machines are doing the sieving in parallel and you want to avoid duplicate work. The most straightforward way is to pick k-1 factors of A randomly, then pick the k_th factor so that the product of all k primes is as close as possible to the optimal A (this is what msieve does).

jasonp

[bsquared]

Thanks for the confirmation! On to the next hurdle...

[R.D. Silverman]

Originally Posted by jasonp

Other authors fix the number of primes making up A and then use a dictionary enumeration algorithm to go through all the combinations of candidate primes

jasonp

One can also treat each of the primes making up A as nodes in a hypercube
and select subsets of them via a Grey code. My code did this a long time
ago (before the SI in SIQS even became common knowledge). I was, at
that time using only a small number of primes (i.e. 4 or 5) in A.