20090525, 07:03  #1 
Aug 2006
1749_{16} Posts 
Polynomial selection
I'm trying to work out how to choose good SNFS polynomials and I thought I'd try to mine the collective wisdom here rather than reinvent the wheel. Feel free to share your own thoughts rather than answer my questions.
1. The ggnfs documentation suggests x^5  200 (SNFS difficulty 146.5) as superior to 4x^5  25 (SNFS difficulty 145.6). This suggests that having a monic polynomial is worth at least 0.9 SNFS difficulty. How far should you go to reduce the leading coefficient? And is going from 2x^5 to x^5 a bugger jump than 4x^5 to 2x^5, or are they the same? (Does being monic mean anything in particular, or is it just that you want to reduce the coefficient as far as reasonable?) 2. What is a good cutoff point for degree 4 and 5? How flexible is the boundary if you have a slightly better degreek polynomial than a degree(k±1) polynomial? Say you have a 100digit number (quartic territory); how much better (in terms of SNFS difficulty) would a quintic need to be to induce a switch? 0.2? 3.0? 3. Is the 135% rule of thumb still approximately correct? 4. What programs are best at SNFS? Are there others I should try? 
20090525, 07:12  #2 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5×19×61 Posts 

20090525, 07:55  #3  
Nov 2008
2×3^{3}×43 Posts 
Quote:
Quote:
Quote:
Quote:
Last fiddled with by 10metreh on 20090525 at 07:58 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial selection  Max0526  NFS@Home  9  20170520 08:57 
Distributed polynomial selection.  chris2be8  Factoring  17  20120427 08:59 
Updated polynomial selection  jasonp  Msieve  65  20110501 19:06 
GNFS polynomial selection  Unregistered  Information & Answers  3  20110416 14:24 
2^8771 polynomial selection  fivemack  Factoring  47  20090616 00:24 