mersenneforum.org SNFS Poly creation for n=2*x^2 - 1
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-29, 15:52 #1 JoeCrump   Oct 2009 North Carolina, USA 10002 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^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!
2009-10-29, 17:28   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

3·11·229 Posts

Quote:
 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.

 2009-10-29, 17:35 #3 frmky     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.
 2009-10-29, 21:00 #4 JoeCrump   Oct 2009 North Carolina, USA 108 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Factoring 7 2015-05-27 23:09 aymanmikhail Soap Box 67 2013-12-09 15:21 ryanp Factoring 6 2013-07-19 17:23 schickel FactorDB 0 2011-12-16 18:07 nuggetprime Factoring 22 2008-08-15 10:01

All times are UTC. The time now is 23:45.

Tue Jun 6 23:45:35 UTC 2023 up 292 days, 21:14, 0 users, load averages: 0.85, 0.78, 0.78