mersenneforum.org SNFS Polynomial for 919^87-1
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-21, 22:21 #1 wblipp     "William" May 2003 New Haven 1001001110012 Posts SNFS Polynomial for 919^87-1 If it survives ECM preparation, what polynomial would you use for 919^87-1? I'm thinking x^6 + 919x^3 + 919^2, x=919^10 That results in SNFS size of 178, which is a little small for a sextic. But for a quintic I only see x^5 + 919^7 * x^2 + 919 x=919^12 and that coefficient of 919^7 looks too large. (Both derived by dividing out 919^29-1 and figuring an SNFS polynomial for 919^58 + 919^29 + 1 Is there something better I have missed?
2011-08-22, 01:40   #2
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by wblipp If it survives ECM preparation, what polynomial would you use for 919^87-1? I'm thinking x^6 + 919x^3 + 919^2, x=919^10 That results in SNFS size of 178, which is a little small for a sextic. But for a quintic I only see x^5 + 919^7 * x^2 + 919 x=919^12 and that coefficient of 919^7 looks too large. (Both derived by dividing out 919^29-1 and figuring an SNFS polynomial for 919^58 + 919^29 + 1 Is there something better I have missed?
Use the sextic.

 2011-08-22, 22:57 #3 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 65010 Posts Here's a poly from factordb for 91987-1 (166 digit cofactor): http://www.factordb.com/snfs.php?id=1100000000225474717 Last fiddled with by Stargate38 on 2011-08-22 at 22:59
2011-08-23, 00:00   #4
frmky

Jul 2003
So Cal

82D16 Posts

Quote:
 Originally Posted by Stargate38 Here's a poly from factordb for 91987-1 (166 digit cofactor): http://www.factordb.com/snfs.php?id=1100000000225474717
This auto-generated polynomial doesn't take advantage of the known algebraic factor. I agree that the original sextic is the obvious choice.

 2011-08-23, 00:11 #5 wblipp     "William" May 2003 New Haven 93916 Posts BAD CHOICE. This is difficulty 258 digits, MUCH MUCH harder than the 178 digits example I gave. It looks like the factordb's polynomial finder needs to learn some tricks about removing algebraic factors. William
2011-08-23, 02:39   #6
bsquared

"Ben"
Feb 2007

2×32×191 Posts

Quote:
 Originally Posted by wblipp It looks like the factordb's polynomial finder needs to learn some tricks about removing algebraic factors. William
Also, something is wrong with the way it picks several of the parameters. Setting mfbr/a to more than twice lpbr/a doesn't make any sense. That will result in many more vain 2LP factorizations. Also, I've never seen r/alambda set so high. I'm less sure that this is bad, but it deviates from the status quo by a couple tenths. Extrapolating from the end of a lookup table, maybe?

2011-08-23, 04:59   #7
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 Originally Posted by Stargate38 Here's a poly from factordb for 91987-1 (166 digit cofactor): http://www.factordb.com/snfs.php?id=1100000000225474717
Quote:
 Originally Posted by frmky This auto-generated polynomial doesn't take advantage of the known algebraic factor. I agree that the original sextic is the obvious choice.
Quote:
 Originally Posted by wblipp BAD CHOICE. This is difficulty 258 digits, MUCH MUCH harder than the 178 digits example I gave. It looks like the factordb's polynomial finder needs to learn some tricks about removing algebraic factors. William
I just posted the above quotes to the factordb thread to make Syd aware of those.

 Similar Threads Thread Thread Starter Forum Replies Last Post mhill12 Factoring 59 2013-09-09 22:40 ryanp Factoring 9 2013-04-03 06:33 wblipp Factoring 4 2011-04-15 16:22 fivemack Factoring 2 2007-07-09 15:09 R.D. Silverman NFSNET Discussion 4 2007-04-11 20:39

All times are UTC. The time now is 14:23.

Wed May 12 14:23:46 UTC 2021 up 34 days, 9:04, 0 users, load averages: 2.67, 2.50, 2.46