mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-05-25, 07:03   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,939 Posts
Default 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?
CRGreathouse is offline   Reply With Quote
Old 2009-05-25, 07:12   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

167916 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
henryzz is offline   Reply With Quote
Old 2009-05-25, 07:55   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
10metreh is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 01:40.

Thu Dec 3 01:40:35 UTC 2020 up 83 days, 22:51, 1 user, load averages: 2.02, 1.80, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.