mersenneforum.org Polynomial selection
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-25, 07:03 #1 CRGreathouse     Aug 2006 22×3×499 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 re-invent 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 degree-k polynomial than a degree-(k±1) polynomial? Say you have a 100-digit 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?
2009-05-25, 07:12   #2
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

17A416 Posts

Quote:
 Originally Posted by CRGreathouse 4. What programs are best at SNFS? Are there others I should try?
ggnfs with msieve postprocessing is what most people use currently
factmsieve.pl is the most common used script

2009-05-25, 07:55   #3
10metreh

Nov 2008

1001000100102 Posts

Quote:
 Originally Posted by CRGreathouse 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 re-invent 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?)
That surprises me. If anything, I'd have thought 4x^5 - 25 with a lower difficulty was superior.

Quote:
 2. What is a good cutoff point for degree 4 and 5? How flexible is the boundary if you have a slightly better degree-k polynomial than a degree-(k±1) polynomial? Say you have a 100-digit 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?
115-120 digits is a rough cutoff for degree 4-5, and test-sieve a small range (say 10k Q) to see which is faster. With difficulty 100, the quartics should be slightly faster than the quintics, but if the quintic is nicer it might be faster. Sometimes you just can't make a quartic for an S100 without increasing the difficulty by 10 or more. In this case, the quintic will probably be faster, or even the sextic (if there is one).

Quote:
 3. Is the 135% rule of thumb still approximately correct?
Depends on the size. The ratio seems to increase with the size. However, you cannot compare SNFS polynomials easily, and some numbers that do have a poly do not have as good a poly as others with a similar difficulty. So the answer is "It depends on the size and the number". Still, it is roughly correct for lower SNFSs.

Quote:
 4. What programs are best at SNFS? Are there others I should try?
I agree with henryzz. Feel free to post in the "Running GGNFS" thread.

Last fiddled with by 10metreh on 2009-05-25 at 07:58

 Similar Threads Thread Thread Starter Forum Replies Last Post Max0526 NFS@Home 9 2017-05-20 08:57 chris2be8 Factoring 17 2012-04-27 08:59 jasonp Msieve 65 2011-05-01 19:06 Unregistered Information & Answers 3 2011-04-16 14:24 fivemack Factoring 47 2009-06-16 00:24

All times are UTC. The time now is 08:46.

Fri Mar 24 08:46:45 UTC 2023 up 218 days, 6:15, 0 users, load averages: 1.14, 0.84, 0.82