mersenneforum.org Strange behavior of polynomial selection
 Register FAQ Search Today's Posts Mark Forums Read

 2008-12-24, 12:15 #1 ET_ Banned     "Luigi" Aug 2002 Team Italia 2×3×17×47 Posts Strange behavior of polynomial selection After a success on a C123 using msieve 1.38, on December 15th I decided to try a factorization of a smallish C104 with Msieve 1.39. I thought I could finish it in less than a week, but after 9 days I'm still at 25%. msieve 1.39 chose the following FB with the standard time constraints: Code: R0: -102172704072372988898 R1: 21141487499 A0: -14062647916862846429413389 A1: 1904450414314729737512 A2: -34268272102003159 A3: -3038101613532 A4: 54319668 A5: 900 skew 30714.64, size 1.720911e-10, alpha -4.946097, combined = 8.949099e-10 FRNUM 170863 FRMAX 2319997 FANUM 170864 FAMAX 2319997 SRLPMAX 67108864 SALPMAX 67108864 SLINE 8400000 msieve had a very fast start, finding 800.000 relations (of the 6M needed) in the first hours of run, then the yield dramatically dropped, and now I am at 30.000 relations/day, slowing down. Before wasting more time, I'm asking: is the chosen selection correct? Should I run polynomial stage for more than the indicated time to look for better selections? My question arises from the information related to the new improved poly selection that comes with v1.39 of msieve: has it been improved for larger composites only? Luigi Last fiddled with by ET_ on 2008-12-24 at 12:17
 2008-12-24, 12:39 #2 Andi47     Oct 2004 Austria 2×17×73 Posts I always import my msieve-found polynomials to GGNFS, for your poly this would look like this: Code: n: Y0 -102172704072372988898 Y1 21141487499 c0 -14062647916862846429413389 c1 1904450414314729737512 c2 -34268272102003159 c3 -3038101613532 c4 54319668 c5 900 skew: 30714.64 rlim: 2300000 alim: 2300000 lpbr: 26 lpba: 26 rlambda: 2.6 alambda: 2.6 mfbr: 49 mfba: 49 I think with these parameters you should need ~5-6M relations. Edit: The smallest composite I GNFSed with a msieve-found poly was a c120, the largest was c136, so I don't know how msieve-found polys behave for smaller composites. Last fiddled with by Andi47 on 2008-12-24 at 12:43
 2008-12-24, 12:48 #3 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 5·19·61 Posts if you import the msieve poly into ggnfs i would expect it to finish in ~8hours for a C104 small GNFSes have been done with msieve poly selection Last fiddled with by henryzz on 2008-12-24 at 12:49
2008-12-24, 12:59   #4
10metreh

Nov 2008

44228 Posts

Quote:
 Originally Posted by henryzz if you import the msieve poly into ggnfs i would expect it to finish in ~8hours for a C104 small GNFSes have been done with msieve poly selection
...including a C97 by none other than me.

ET_, your alpha of -4.9 is much worse than all three alphas I have got using msieve poly selection. My C97 gave a poly with an alpha of -5.8, with a few better than -6.

Last fiddled with by 10metreh on 2008-12-24 at 13:01

2008-12-24, 13:20   #5
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·3·17·47 Posts

Quote:
 Originally Posted by 10metreh ...including a C97 by none other than me. ET_, your alpha of -4.9 is much worse than all three alphas I have got using msieve poly selection. My C97 gave a poly with an alpha of -5.8, with a few better than -6.
I'd like to stick on msieve when possible. Jason deserves it

Thank you to all who answered my post, and merry Christmas.

Luigi

 2008-12-24, 14:45 #6 jasonp Tribal Bullet     Oct 2004 2×3×19×31 Posts There's nothing wrong with the polynomial chosen, sometimes a polynomial has excellent size properties but only moderately good root properties. What matters is how well both work together. The problem is that this polynomial wants a sieving region skewed by a factor of about 30000, meaning the 'a' values in relations average 30k times larger than the 'b' values. It also means that the polynomial will generate a huge number of relations as long as 'b' is very small, but will stop doing so once 'b' starts to get larger. The line sieve in msieve has no idea that this is happening. Luigi, while I appreciate the vote of confidence, there is no substitute for the lattice siever in GGNFS. Using it would make the difference between taking forever and being done very quickly.

 Similar Threads Thread Thread Starter Forum Replies Last Post Max0526 NFS@Home 9 2017-05-20 08:57 fivemack Factoring 47 2009-06-16 00:24 jwh Information & Answers 1 2009-01-30 18:04 jinydu Lounge 23 2004-06-08 09:00 willmore Software 0 2002-09-09 20:17

All times are UTC. The time now is 06:33.

Tue Jan 26 06:33:46 UTC 2021 up 54 days, 2:45, 0 users, load averages: 2.55, 2.57, 2.57