Msieve 1.42 feedback

[Jeff Gilchrist]

I have tried to do poly selection on 6 GNFS numbers with 1.42beta on 64bit Linux and two of the runs have completed "polynomial selection complete , elapsed time XX:XX:XX" without any polynomial.

The msieve.fb file is 0 bytes, and msieve doesn't print the polynomial in the msieve.log file or to stdout. The first one was a small C118 and the second a C131. There are no indications as to what happened with the C131, but the C118 has this error in the stdout:
polynomial selection complete
error generating or reading NFS polynomials
elapsed time 03:06:57


The msieve.log is:

Tue Jun  9 10:50:40 2009  Msieve v. 1.42
Tue Jun  9 10:50:40 2009  random seeds: ec20192f 6443e1cb
Tue Jun  9 10:50:40 2009  factoring 1195889777350299605771289107018392405410588807124263934343162265572375663837663946874692414404316491260057477983979093 (118 digits)
Tue Jun  9 10:50:41 2009  no P-1/P+1/ECM available, skipping
Tue Jun  9 10:50:41 2009  commencing number field sieve (118-digit input)
Tue Jun  9 10:50:41 2009  commencing number field sieve polynomial selection
Tue Jun  9 10:50:41 2009  time limit set to 2.75 hours
Tue Jun  9 10:50:41 2009  searching leading coefficients from 1 to 23810
Tue Jun  9 13:57:37 2009  polynomial selection complete
Tue Jun  9 13:57:37 2009  elapsed time 03:06:57

[Andi47]

Originally Posted by Jeff Gilchrist

I have tried to do poly selection on 6 GNFS numbers with 1.42beta on 64bit Linux and two of the runs have completed "polynomial selection complete , elapsed time XX:XX:XX" without any polynomial.

The msieve.fb file is 0 bytes, and msieve doesn't print the polynomial in the msieve.log file or to stdout. The first one was a small C118 and the second a C131. There are no indications as to what happened with the C131, but the C118 has this error in the stdout:
polynomial selection complete
error generating or reading NFS polynomials
elapsed time 03:06:57


The msieve.log is:

Tue Jun  9 10:50:40 2009  Msieve v. 1.42
Tue Jun  9 10:50:40 2009  random seeds: ec20192f 6443e1cb
Tue Jun  9 10:50:40 2009  factoring 1195889777350299605771289107018392405410588807124263934343162265572375663837663946874692414404316491260057477983979093 (118 digits)
Tue Jun  9 10:50:41 2009  no P-1/P+1/ECM available, skipping
Tue Jun  9 10:50:41 2009  commencing number field sieve (118-digit input)
Tue Jun  9 10:50:41 2009  commencing number field sieve polynomial selection
Tue Jun  9 10:50:41 2009  time limit set to 2.75 hours
Tue Jun  9 10:50:41 2009  searching leading coefficients from 1 to 23810
Tue Jun  9 13:57:37 2009  polynomial selection complete
Tue Jun  9 13:57:37 2009  elapsed time 03:06:57

Maybe something related to the "expansion failed" error? I have never seen this in 1.41 (but every factorization gives few "integrator failed" errors), but they occur quite frequently in 1.42 beta. With 1.42 beta, I had a c118 (or was ist c115?) which had ~30 (or even more) "expansion failed" errors in a row.

[jasonp]

Try defining CHECK in gnfs/poly/stage1/stage1_sieve.c and gnfs/poly/stage2/stage2.c to see whether it's finding any candidates at all. The 'expand failed' messages don't indicate a problem; v1.41 had them too, it just never complained about it.

[Jeff Gilchrist]

I'm not sure. I re-ran it, so a different random seed was used and it completed this time.

Wed Jun 10 08:55:21 2009 skew 313421.41, size 3.386368e-11, alpha -6.878168, combined = 4.264490e-10
Wed Jun 10 08:55:21 2009 elapsed time 03:07:27

[jasonp]

Poly selection doesn't use random numbers. Hmm...

If you still have the console output, did it search the same coeff ranges the second time?

[Jeff Gilchrist]

Originally Posted by jasonp

Poly selection doesn't use random numbers. Hmm...

If you still have the console output, did it search the same coeff ranges the second time?

Here is the output from the second run that worked:

Wed Jun 10 12:34:01 2009  Msieve v. 1.42
Wed Jun 10 12:34:01 2009  random seeds: 5b6caa19 2afd0808
Wed Jun 10 12:34:01 2009  factoring 1195889777350299605771289107018392405410588807124263934343162265572375663837663946874692414404316491260057477983979093 (118 digits)
Wed Jun 10 12:34:02 2009  no P-1/P+1/ECM available, skipping
Wed Jun 10 12:34:02 2009  commencing number field sieve (118-digit input)
Wed Jun 10 12:34:02 2009  commencing number field sieve polynomial selection
Wed Jun 10 12:34:02 2009  time limit set to 2.75 hours
Wed Jun 10 12:34:02 2009  searching leading coefficients from 1 to 23810
Wed Jun 10 15:40:55 2009  polynomial selection complete
Wed Jun 10 15:40:55 2009  R0: -60794761235931305858261
Wed Jun 10 15:40:55 2009  R1:  3627134324033
Wed Jun 10 15:40:55 2009  A0: -761409855711500147961913211328
Wed Jun 10 15:40:55 2009  A1:  1573674781252174207911944
Wed Jun 10 15:40:55 2009  A2:  29841396216635953558
Wed Jun 10 15:40:55 2009  A3: -361694064195745
Wed Jun 10 15:40:55 2009  A4: -118042956
Wed Jun 10 15:40:55 2009  A5:  1440
Wed Jun 10 15:40:55 2009  skew 313421.41, size 3.386368e-11, alpha -6.878168, combined = 4.264490e-10
Wed Jun 10 15:40:55 2009  elapsed time 03:06:54

So it says it did the same range of 1 to 23810.

Jeff.

[10metreh]

I have just had this on a filtering run for a c102:

Sat Jun 20 10:49:24 2009  commencing singleton removal, final pass
Sat Jun 20 10:51:48 2009  memory use: 18.6 MB
Sat Jun 20 10:51:49 2009  commencing in-memory singleton removal
Sat Jun 20 10:51:50 2009  begin with 986754 relations and 914620 unique ideals
Sat Jun 20 10:51:53 2009  reduce to 439590 relations and 330369 ideals in 32 passes
Sat Jun 20 10:51:53 2009  max relations containing the same ideal: 10
Sat Jun 20 10:51:55 2009  reading rational ideals above 100000
Sat Jun 20 10:51:55 2009  reading algebraic ideals above 100000
Sat Jun 20 10:51:55 2009  commencing singleton removal, final pass
Sat Jun 20 10:55:37 2009  keeping 550954 ideals with weight <= 25, new excess is 23139
Sat Jun 20 10:56:13 2009  memory use: 17.1 MB
Sat Jun 20 10:56:28 2009  commencing in-memory singleton removal
Sat Jun 20 10:56:29 2009  begin with 440118 relations and 550954 unique ideals
Sat Jun 20 10:56:32 2009  reduce to 93 relations and 0 ideals in 19 passes
Sat Jun 20 10:56:32 2009  max relations containing the same ideal: 0
Sat Jun 20 10:56:32 2009  filtering wants 80244 more relations
Sat Jun 20 10:56:32 2009  elapsed time 00:19:11

The relations I had were almost certainly not enough (3.5M), but should I expect this type of behaviour?

[Andi47]

Originally Posted by 10metreh

I have just had this on a filtering run for a c102:

Sat Jun 20 10:56:32 2009  reduce to 93 relations and 0 ideals in 19 passes

Sat Jun 20 10:56:32 2009  max relations containing the same ideal: 0
Sat Jun 20 10:56:32 2009  filtering wants 80244 more relations

The relations I had were almost certainly not enough (3.5M), but should I expect this type of behaviour?

Yes, this behaviour indicates that you are still far from enough relations - and you certainly need much more than 80244 more relations.

[10metreh]

Originally Posted by Andi47

Yes, this behaviour indicates that you are still far from enough relations - and you certainly need much more than 80244 more relations.

I understand that. Will I need about 6M rels?

[Andi_HB]

i don`t think so. My last c102 factorization needs less than 4 Million relations.


N= C102, special Q range size = 600000 , number of relations = 3981204

edit: this number was done in total time 4,5 hours on core 2 duo

Regards Andi_HB

[10metreh]

Sorry, 6M was a typo for 5M. Hopefully it'll be finished before I go on holiday on Monday