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 3×787 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

164448 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 23·34 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

82416 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 3×787 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

22×853 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 21:39.

Wed Apr 21 21:39:07 UTC 2021 up 13 days, 16:19, 0 users, load averages: 2.40, 1.98, 1.85