SNFS Polynomial for 919^87-1

[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?

[R.D. Silverman]

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.

[Stargate38]

Here's a poly from factordb for 919⁸⁷-1 (166 digit cofactor): http://www.factordb.com/snfs.php?id=1100000000225474717

[frmky]

Originally Posted by Stargate38

Here's a poly from factordb for 919⁸⁷-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.

[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

[bsquared]

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?

[Andi47]

Originally Posted by Stargate38

Here's a poly from factordb for 919⁸⁷-1 (166 digit cofactor): http://www.factordb.com/snfs.php?id=1100000000225474717

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.

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.