20070223, 22:07  #1 
"Ben"
Feb 2007
3,361 Posts 
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. 
20070225, 20:27  #2  
Tribal Bullet
Oct 2004
2×3×19×31 Posts 
Quote:
Quote:
jasonp 

20070228, 14:14  #3 
"Ben"
Feb 2007
3,361 Posts 
Thanks for the confirmation! On to the next hurdle...

20070228, 14:22  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
msieve parallel poly selection with MPI  drone84  Msieve  4  20170628 09:18 
GNFS poly selection  frmky  Factoring  14  20120723 01:57 
C138 poly selection  firejuggler  Aliquot Sequences  1  20110221 06:38 
Restart/continue poly selection with msieve?  Jeff Gilchrist  Msieve  3  20090425 14:03 
Different msieve 1.39 poly selection outputs...  Jeff Gilchrist  Msieve  5  20081229 23:07 