SNFS Poly creation for n=2*x^2 - 1

[JoeCrump]

I have a few ~C180s I need to factor. ECM has already run upto B1=11mil bound so I'm looking to finish with SNFS if possible. The problem I'm having is that the polynomials I'm creating do not give good performance (i.e. compared to other numbers I've done with SNFS which were of the form r^e-s). I'm wondering why and whether someone can advise a better approach to creating polynomials for these.

Let me give a specific example:

c159 = 943678541557242360267381078142531725184939371179933110685996787133278689060023639358856607979737887292422703591189986894750771044325960544955770926525312874129;

This is a remaining composite from (2*x^2 - 1) where x=10^86 + 39022535;

Now, my experience from NFS in the past has been to create a 4, 5, or 6 degree polynomial through adding factors. With this number I started by letting y=10^43 and creating the quartic...

2*y^4 + 156090140*y^2 + 3045516475652449

However, this seems to give poor performance (~1rels/sec) when I feed into GGNFS.

c4: 2
c2: 156090140
c0: 3045516475652449
Y1: 1
Y0: -10000000000000000000000000000000000000000000
skew: 6246.801981814374240029413779

I tried also making the leading coefficient a 1 by using:
y = 2*10^43;
y^4 + 312180280*y^2 + 24364131805219592

That didn't do any better. Then I tried a sextic with:
c6: 1
c3: 780450700000
c0: 152275823782622450000000
Y1: 1
Y0: -1000000000000000000000000000000

which also gives poor performance. I'm interested in learning why these polynomials don't work well and what is a better approach for creating polynomials when you have a simple quadratic form for the number.

Thanks much for your expert advice!

[R.D. Silverman]

Originally Posted by JoeCrump

This is a remaining composite from (2*x^2 - 1) where x=10^86 + 39022535;

Now, my experience from NFS in the past has been to create a 4, 5, or 6 degree polynomial through adding factors. With this number I started by letting y=10^43 and creating the quartic...

2*y^4 + 156090140*y^2 + 3045516475652449

However, this seems to give poor performance
That didn't do any better. Then I tried a sextic with:
c6: 1
c3: 780450700000
c0: 152275823782622450000000
Y1: 1
Y0: -1000000000000000000000000000000

which also gives poor performance. I'm interested in learning why these polynomials don't work well
!

They give relatively poor performance relative to similar sized numbers
also done by SNFS because the coefficients of your polynomials are BIG.

Look at the norms of the integers generated by your polynomials.

With coefficients this big, you are really running GNFS and not SNFS.

[frmky]

The think the best you can do is the sextic:

c6: 2
c3: 312180280
c0: 12182065902609796
Y1: 1
Y0: -100000000000000000000000000000

But this is still a huge c0 coefficient, making the algebraic norm 15 digits larger than normal. It's really closer to a GNFS factorization. Be sure to sieve on the algebraic side and make the alim much larger than the rlim.

[JoeCrump]

Thanks for the replies. I appreciate it. I guess I haven't done enough SNFS yet to get a feel for how the performance is affected by the increase in coefficient size! The numbers didn't look "that" big to me, but understand it's much bigger than the usual SNFS targets.