mersenneforum.org SNFS Polynomial for 919^87-1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-21, 22:21 #1 wblipp     "William" May 2003 New Haven 23·5·59 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

22×5×373 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 72·13 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

23×257 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 236010 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

D2116 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

46628 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.

 Thread Tools

 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 03:18.

Tue Jan 26 03:18:37 UTC 2021 up 53 days, 23:29, 0 users, load averages: 1.15, 1.54, 1.63

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