mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-02-23, 22:07   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

25×3×5×7 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?

Thanks,
ben.
bsquared is offline   Reply With Quote
Old 2007-02-25, 20:27   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Quote:
Originally Posted by bsquared View Post
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).
Quote:
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
jasonp is offline   Reply With Quote
Old 2007-02-28, 14:14   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

25×3×5×7 Posts
Default

Thanks for the confirmation! On to the next hurdle...
bsquared is offline   Reply With Quote
Old 2007-02-28, 14:22   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
msieve parallel poly selection with MPI drone84 Msieve 4 2017-06-28 09:18
GNFS poly selection frmky Factoring 14 2012-07-23 01:57
C138 poly selection firejuggler Aliquot Sequences 1 2011-02-21 06:38
Restart/continue poly selection with msieve? Jeff Gilchrist Msieve 3 2009-04-25 14:03
Different msieve 1.39 poly selection outputs... Jeff Gilchrist Msieve 5 2008-12-29 23:07

All times are UTC. The time now is 18:57.

Fri Jan 15 18:57:32 UTC 2021 up 43 days, 15:08, 0 users, load averages: 2.98, 3.15, 2.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.