mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-08-21, 22:21   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default 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?
wblipp is offline   Reply With Quote
Old 2011-08-22, 01:40   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by wblipp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-08-22, 22:57   #3
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

64810 Posts
Default

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
Stargate38 is offline   Reply With Quote
Old 2011-08-23, 00:00   #4
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

1000001000112 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
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.
frmky is offline   Reply With Quote
Old 2011-08-23, 00:11   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2011-08-23, 02:39   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×23×37 Posts
Default

Quote:
Originally Posted by wblipp View Post

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?
bsquared is offline   Reply With Quote
Old 2011-08-23, 04:59   #7
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
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 View Post
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 View Post
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.
Andi47 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS Polynomial selection help? mhill12 Factoring 59 2013-09-09 22:40
SNFS polynomial with very low yield ryanp Factoring 9 2013-04-03 06:33
How To Evaluate SNFS Polynomial Tricks? wblipp Factoring 4 2011-04-15 16:22
Concocting an SNFS polynomial for 2^2376-1 fivemack Factoring 2 2007-07-09 15:09
SNFS Polynomial R.D. Silverman NFSNET Discussion 4 2007-04-11 20:39

All times are UTC. The time now is 11:36.

Tue Apr 20 11:36:28 UTC 2021 up 12 days, 6:17, 0 users, load averages: 1.79, 1.90, 1.93

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.