mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2008-12-24, 12:15   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×3×17×47 Posts
Default 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
ET_ is offline   Reply With Quote
Old 2008-12-24, 12:39   #2
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

I always import my msieve-found polynomials to GGNFS, for your poly this would look like this:

Code:
n: <insert your number here>
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
Andi47 is offline   Reply With Quote
Old 2008-12-24, 12:48   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5·19·61 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2008-12-24, 12:59   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

44228 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
10metreh is offline   Reply With Quote
Old 2008-12-24, 13:20   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·3·17·47 Posts
Default

Quote:
Originally Posted by 10metreh View Post
...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
ET_ is offline   Reply With Quote
Old 2008-12-24, 14:45   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial selection Max0526 NFS@Home 9 2017-05-20 08:57
2^877-1 polynomial selection fivemack Factoring 47 2009-06-16 00:24
Very strange mem timing behavior, Asus M3A67-EM jwh Information & Answers 1 2009-01-30 18:04
Strange Computer Behavior jinydu Lounge 23 2004-06-08 09:00
Strange behavior on 1.7G Celeron 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.