Msieve 1.42 feedback

[10metreh]

Originally Posted by 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

I actually needed 4.6M rels (although the Q range was 600000 for me too).

[10metreh]

I got an error similar to Jeff Gilchrist where no polynomials were found (this was a while ago, I forgot to report it). The difference from that error is in red:

Sat Jun 27 09:00:10 2009  
Sat Jun 27 09:00:10 2009  
Sat Jun 27 09:00:10 2009  Msieve v. 1.42
Sat Jun 27 09:00:10 2009  random seeds: cea0ec0c 4f3746d2
Sat Jun 27 09:00:10 2009  factoring 11991192823388868367155552793680436282579888088321632095024669721174814820718076050614397759807681281671 (104 digits)
Sat Jun 27 09:00:13 2009  searching for 15-digit factors
Sat Jun 27 09:00:16 2009  commencing number field sieve (104-digit input)
Sat Jun 27 09:00:16 2009  commencing number field sieve polynomial selection
Sat Jun 27 09:00:16 2009  time limit set to 0.46 hours
Sat Jun 27 09:00:16 2009  searching leading coefficients from 1 to 4751
Sat Jun 27 09:28:09 2009  polynomial selection complete
Sat Jun 27 09:28:09 2009  warning: polynomial is corrupt
Sat Jun 27 09:28:09 2009  elapsed time 00:27:59

I then ran pol51 which succeeded in producing a poly (actually, loads), and the number factored as p45*p59. I have not retried with msieve yet.

[jasonp]

Hmm, running this number locally yields 27 polynomials, the best of which is

R0: -85398939277729522479
R1:  37108786657
A0: -185375015660047120018300
A1: -278006898695002742560
A2:  39598619425934907
A3:  2227616029938
A4: -54872374
A5:  2640
skew 14244.59, size 7.796719e-010, alpha -5.082192, combined = 2.311560e-009

Stage 1 finds loads of possibilities, but unusually few of them seem to make it through stage 2.

[axn]

Originally Posted by jasonp

Stage 1 finds loads of possibilities, but unusually few of them seem to make it through stage 2.

How does msieve use the "cutoff time"? (I mean, not all processors are created equal)

[henryzz]

Originally Posted by axn

How does msieve use the "cutoff time"? (I mean, not all processors are created equal)

yes it is quite possible that 10metreh used his old p4 which would do quite a bit less work in the same time than a lot of pcs
try underclocking your pc and see if it produces any polynomials unless you have some old ones still

[10metreh]

Originally Posted by henryzz

yes it is quite possible that 10metreh used his old p4 which would do quite a bit less work in the same time than a lot of pcs
try underclocking your pc and see if it produces any polynomials unless you have some old ones still

I did use the old P4, but msieve searched right up to the leading coefficient limit of 4751. I have had msieve finish in way under the time limit for some numbers and I have had it take far longer. I have no idea what the time limit actually does.

[jasonp]

The time limit is probably to blame; the search space with Kleinjung's algorithm is so large that it's infeasible to search the entire space unless you drastically limit its size at the outset or the number being factored is quite small. You can also increase the size of the search space that pol5 uses, but its efficiency degrades if you do so.

I don't have a feeling for how the space should be limited, short of assuming that you want to search around 100 a5 values and the total time should add up to maybe 5% of the sieving time. So the total time is limited, and the time for each a5 is limited too. a5 values that run on slower computers, or a5 values that are rich in polynomials found, thus get artificially constrained in how far the search goes. If the search space is small enough to be exhausted, msieve will quit early.

[Batalov]

The Lanczos integrity check is an absolutely invaluable addition in 1.42-beta2 for those using home (not server) computers. Without ECC, and in the heat of the summer, even on prime95-stable PCs, errors happen silently and differently from prime95: different subsystems are stressed.

If one is to run a 10-day or even a 2-3-month Block Lanczos run, just imagine how much time will now be saved. You get a message to restart from an earlier .chk file and instead of "waiting" for the 101% progress report to restart from the beginning (as you would have before).

Thank you, Jason! Great stuff!

[jrk]

Oops I found a bug in beta 2.

In check_excess in file gnfs/filter/filter.c:80, relations_needed is being redefined inside the if block although it is already defined above it, and so the return after the block always returns 0 even when there are relations needed.

This diff fixes it:

diff -udr msieve-1.42.orig/gnfs/filter/filter.c msieve-1.42/gnfs/filter/filter.c
--- msieve-1.42.orig/gnfs/filter/filter.c	2009-07-07 14:28:29.000000000 -0500
+++ msieve-1.42/gnfs/filter/filter.c	2009-07-07 22:59:15.749878366 -0500
@@ -77,7 +77,7 @@
 	if (filter->num_relations < filter->num_ideals ||
 	    filter->num_relations - filter->num_ideals < 
 	    				filter->target_excess) {
-		uint32 relations_needed = 1000000;
+		relations_needed = 1000000;
 
 		if (filter->num_relations > filter->num_ideals) {
 			relations_needed = 3 * (filter->target_excess -

The bug manifested itself as a null pointer dereference in common/filter/merge_pre.c:42.

[jrk]

Now I have hit another bug.

In filter_purge_singletons_core in file common/filter/singleton.c:410, there is an out-of-bounds array access. ideal = 4294967295 (-1).

If you want I can send you the msieve.dat and msieve.fb files.

[jrk]

line number ++

Originally Posted by jrk

In filter_purge_singletons_core in file common/filter/singleton.c:411, there is an out-of-bounds array access. ideal = 4294967295 (-1).