20091029, 15:52  #1 
Oct 2009
North Carolina, USA
1000_{2} Posts 
SNFS Poly creation for n=2*x^2  1
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^es). 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! 
20091029, 17:28  #2  
"Bob Silverman"
Nov 2003
North of Boston
3·11·229 Posts 
Quote:
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. 

20091029, 17:35  #3 
Jul 2003
So Cal
2,647 Posts 
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. 
20091029, 21:00  #4 
Oct 2009
North Carolina, USA
10_{8} Posts 
Thanks
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How To Calculate SNFS Poly?  Stargate38  Factoring  7  20150527 23:09 
Creation Museum  aymanmikhail  Soap Box  67  20131209 15:21 
SNFS poly for b^n1, n prime?  ryanp  Factoring  6  20130719 17:23 
Ooops....SNFS poly for primes?  schickel  FactorDB  0  20111216 18:07 
Homogeneous Cunningham snfs poly selection?  nuggetprime  Factoring  22  20080815 10:01 