[quote=smh;170155]Next time, attach the log and only post the relevant lines between code tags.

[URL]http://www.mersenneforum.org/showpost.php?p=169144&postcount=20[/URL][/quote]

Done.

How many more relations should I need? Would 100000 more be sufficient? (And btw, the ~3000 removed rels are still there - I did use the new -nc1 X,Y switch.)

Filtering after GNFS is a peculiar animal
 

[QUOTE=jasonp;170158]
Fixing this problem requires either making the filtering produce a matrix that is deliberately larger, or making the filtering smart enough to realize this is about to happen.
[/QUOTE]

IMO, the current filtering strategy has one nice side-effect on GNFS jobs: I sometimes get a nice, solvable matrix even though I began filtering with fewer relations than large ideals. So this sensitivity to clumps of heavy columns may have its upside, in that it has gotten me to the finish line with a bare minimum of sieving.

Just to let you know, I added ~200000 more relations and ended up with a nice matrix, with the factors being p47*p49.

[quote=Batalov;170156]As the number of collected relations grows, there are four "zones":
1) far too few relations; then -nc1 doesn't produce cycles and asks for more relns => Sieve some more;
2) [SIZE=1](rarely visited; you are here!)[/SIZE] almost enough relations; -nc1 makes cycles, -nc2 builds a matrix, cleans it up and then the matrix is not useable => Sieve some more;
3) convergent zone; here's some freedom of choice: with more relns, the matrix gets better and better, but it is well established that you generally do not save any overall time anymore => Build the matrix and do -nc2, -nc3
4) far too many relations => trim free relations from the end of .dat file (these are short lines), then trim some more, goto zone 3). But not too much or you will end up in zones 1-2)[/quote]
Is there any way of knowing how wide or thin zone 3 will be?

The rule of thumb seems to be that the largest number of relations that lets the filtering converge is ~2x the number of relations needed to build a matrix at all. I know that Greg tried a small job with ~2.5x this number, and the filtering barely did not converge.

QS doesn't have this problem, because the filtering there is much simpler. Simple enough that it can determine the exact moment you move from zone 1 to zone 2. Unfortunately, because it's so simple it cannot recover if you do distributed sieving and wind up far into zone 3 by accident.

[quote=jasonp;170391]QS doesn't have this problem, because the filtering there is much simpler. Simple enough that it can determine the exact moment you move from zone 1 to zone 2. Unfortunately, because it's so simple it cannot recover if you do distributed sieving and wind up far into zone 3 by accident.[/quote]

I was surprised when I ran into this case for the C130 I did. The distributed QS ended up hugely oversieving, but msieve filtered and built the matrix just fine. The number of relns was slightly bigger than 2x the amount needed.

Unlike NFS, far more time was spent oversieving than was gained by any LA time improvement due the the improved matrix.

There seems to be some problem with false ecm positives:

[code]
[...]
Mon Apr 27 07:48:43 2009 Msieve v. 1.41
Mon Apr 27 07:48:43 2009 random seeds: 338dd7a0 2f961bb5
Mon Apr 27 07:48:43 2009 factoring 638096014932228224302452016064507063802324654595415081901358898974901285836769791479594533815276970539801031498914466415956783 (126 digits)
Mon Apr 27 07:48:44 2009 searching for 15-digit factors
[b]
Mon Apr 27 07:48:44 2009 ECM stage 1 factor found
Mon Apr 27 07:48:44 2009 ECM stage 1 factor found
Mon Apr 27 07:48:44 2009 ECM stage 1 factor found
[/b]
Mon Apr 27 07:48:44 2009 commencing number field sieve (126-digit input)
Mon Apr 27 07:48:44 2009 R0: -1861339942809298858475914
Mon Apr 27 07:48:44 2009 R1: 63877241236117
Mon Apr 27 07:48:44 2009 A0: -23309507144277607290425987625
Mon Apr 27 07:48:44 2009 A1: 3137920371646445657587182
Mon Apr 27 07:48:44 2009 A2: 609192173713697200
Mon Apr 27 07:48:44 2009 A3: -1795121412471184
Mon Apr 27 07:48:44 2009 A4: -1256950393
Mon Apr 27 07:48:44 2009 A5: 28560
Mon Apr 27 07:48:44 2009 skew 92106.78, size 4.010604e-012, alpha -4.714407, combined = 1.324735e-010
Mon Apr 27 07:48:44 2009
Mon Apr 27 07:48:44 2009 commencing square root phase
Mon Apr 27 07:48:44 2009 reading relations for dependency 1
Mon Apr 27 07:48:44 2009 read 599592 cycles
Mon Apr 27 07:48:45 2009 cycles contain 2573387 unique relations
Mon Apr 27 07:49:01 2009 read 2573387 relations
Mon Apr 27 07:49:09 2009 multiplying 2141818 relations
Mon Apr 27 07:52:21 2009 multiply complete, coefficients have about 97.49 million bits
Mon Apr 27 07:52:23 2009 initial square root is modulo 9945647
Mon Apr 27 07:56:23 2009 sqrtTime: 459
Mon Apr 27 07:56:23 2009 prp47 factor: 32414429228082667877114805561517386090449094571
Mon Apr 27 07:56:23 2009 prp80 factor: 19685554554803184186969721135651921249315138724861905836197134437926560551276173
Mon Apr 27 07:56:23 2009 elapsed time 00:07:40
[/code]

[QUOTE=mklasson;171134]There seems to be some problem with false ecm positives:
[/QUOTE]
I've seen this in another logfile too, and have not been able to reproduce it locally. My guess is that sometimes ECM finds a factor N of the input N, even when N has no small factors. The GMP-ECM stub gives up after this happens three times (it assumes there's a small factor and the ECM parameters are too conservative).

Alex: is the above possible, and if so then is it possible that some inputs would make ECM find a factor of N multiple times even with different starting seeds?

Hard to tell what's happening. It's impossible that three sigma were chosen by chance so that the order of the curve was smooth for both factors (but never for only one of them). Mklasson, is this error reproducible? If yes, maybe we can add some diagnotic output to msieve's smallfact/the GMP-ECM code. And which version of GMP-ECM and which cpu type do you use?

Alex

I've seen that too but I have no idea now which number it might have been. I can start digging if you think it would help.

[QUOTE=akruppa;171138]And which version of GMP-ECM and which cpu type do you use?
[/QUOTE]
The v1.41 binary for 32-bit windows uses GMP-ECM v6.2.2 and (I think) GMP v4.2.1, both built with MinGW.

PS: The recent odd-perfect-related factorization by ATH [url="http://mersenneforum.org/showthread.php?t=11680"]here[/url] also had this problem, and I also cannot reproduce it locally.