Running Msieve

[Andi47]

Originally Posted by jasonp

Now available. Major changes include:

Can version 1.18 continue NFS and SIQS factorisations started with 1.17? Or is it more save to start a NFS factorisation from scratch when using 1.18?

Edit: Are you planning to introduce a lattice siever for NFS?

P.S.: My factorisations which are running almost continuously on a Core 2 Duo @ 2 GHz (see post#50) are currently at:

GNFS on a c120: 1433279 relations, need 7171675 (20.0% of sieving)
SIQS on a c121: 100873 relations, need 435096 (23.2% of sieving)

[jasonp]

Originally Posted by Andi47

Can version 1.18 continue NFS and SIQS factorisations started with 1.17? Or is it more save to start a NFS factorisation from scratch when using 1.18?

Edit: Are you planning to introduce a lattice siever for NFS?

P.S.: My factorisations which are running almost continuously on a Core 2 Duo @ 2 GHz (see post#50) are currently at:

GNFS on a c120: 1433279 relations, need 7171675 (20.0% of sieving)
SIQS on a c121: 100873 relations, need 435096 (23.2% of sieving)

v1.18 has no QS changes, and no NFS changes in the sieving (that matter here), so it's safe to restart with the new version. I'm planning on adding a lattice siever, but I think there are many polynomial selection ideas that appear in papers but have never appeared in code, and I want to try doing that first. You can always use GGNFS for the sieving, it's much faster given msieve's current state.

jasonp

[fivemack]

So, I've constructed a file s4800.1330.msieve_in saying

N 111301495713345998565054568015959546279594064967499789853627559376296769966740283092171586472704831346961354688986449068047
R0 -483780634987846269271231
R1  21544518275869
A0  6068633328002536070769101100
A1  1427075948409623348021150
A2  57820472618486289266
A3 -191946364995859
A4  2021581028
A5  4200

I have a file s4800.1330.rels, of 5.5 million lines, the first few of which are

-276552830,2003:1A4C5,2766B,418C79,5D702B,D,A3:2f87039,270359,4E19,2E83B,14697B,3,5,5,7,1D,3B,1A3,2,2,2,2,2,2,2,1E849D
-986053286,6997:8105381,301e259,2429,20C77,3,7,13:2d57239,1A7F1,67B91,A4917,F619F,1FB5,923,5,61,9D,2,2,2,1E849D
2199566,99:3afef55,2BFD,5310D,C5F,71F,5,7:4746d9,4bb8c4b,5345,6DA5,11,13,1D,1F,C7,3,2,2,2,1E849D

and I say

LD_LIBRARY_PATH=/home/fivemack/maths/gsl-installation/lib ./msieve -v -nc -i s4800.1330.msieve_in -s s4800.1330.rels

but I get a message "error generating or reading NFS polynomials"

I've had a brief look at the source code, but it is 1:30 and my brain not work good at the moment; I guess I've just got the syntax slightly wrong. Please help me.

[my actual goal is to use this on a 200-digit SNFS on which ggnfs's procrels reliably screws up horribly, but I wanted to try with an example of less than fifty million relations first]

[jasonp]

Originally Posted by fivemack

LD_LIBRARY_PATH=/home/fivemack/maths/gsl-installation/lib ./msieve -v -nc -i s4800.1330.msieve_in -s s4800.1330.rels

Your number (by itself) must go into a file that is the argument of '-i', while the file that contains the polynomial should be the argument to '-nf'. Also, the relations file must have 'N <your number>' as its first line.

You will be in unknown territory trying to complete a 200-digit SNFS job. The largest NFS job that I've seen completed had 13.5 million relations. See this post for further details on modifying the source before trying. Do the relations have 64-bit 'a' values? If so, you'll need changes that are only in my current developer source, which I'll release ahead of schedule to encourage these big jobs.

jasonp

[smh]

Hi Jason,

I've been trying to finish a factorization with msieve that was started with GGNFS (which finished the number already btw). It has about SNFS dif. ~130.

I did the following:

- renamed spairs.out to msieve.dat and added N <number> as the first line
- Created worktodo.ini with just the number to factor
- Created msieve.fb as follows

N 407489615500169800857250950565976106355321189765537232596572514940677926345490888565626525440064766633254006824434321250360001
R0  165001001369953155517578125
R1 -1
A0  49
A1  0
A2  0
A3  0
A4  0
A5  5

FRMAX 800000
FAMAX 800000
SRLPMAX 33554432
SALPMAX 33554432
SRTFBITS 44
SATFBITS 44

msieve.dat contains a bit over 1.07M relations (according to GGNFS).

I ran the following command:

msieve -nc -v

which gives me the following output

Thu Apr 26 00:17:08 2007  Msieve v. 1.19
Thu Apr 26 00:17:08 2007  random seeds: ac865ba4 6953cb4f
Thu Apr 26 00:17:08 2007  factoring 407489615500169800857250950565976106355321189765537232596572514940677926345490888565626525440064766633254006824434321250360001 (126 digits)
Thu Apr 26 00:17:08 2007  commencing number field sieve (126-digit input)
Thu Apr 26 00:17:08 2007  R0:  165001001369953155517578125
Thu Apr 26 00:17:08 2007  R1: -1
Thu Apr 26 00:17:08 2007  A0:  49
Thu Apr 26 00:17:08 2007  A1:  0
Thu Apr 26 00:17:08 2007  A2:  0
Thu Apr 26 00:17:08 2007  A3:  0
Thu Apr 26 00:17:08 2007  A4:  0
Thu Apr 26 00:17:08 2007  A5:  5
Thu Apr 26 00:17:08 2007  size score = 4.077204e-009, Murphy alpha = -0.049708, combined = 4.145324e-009
Thu Apr 26 00:17:09 2007  restarting with 171299 relations
Thu Apr 26 00:17:09 2007  generating factor base
Thu Apr 26 00:17:09 2007  factor base complete:
Thu Apr 26 00:17:09 2007  63951 rational roots (max prime = 799999)
Thu Apr 26 00:17:09 2007  63758 algebraic roots (max prime = 799999)
Thu Apr 26 00:17:09 2007  added 3154 free relations
Thu Apr 26 00:17:09 2007  
Thu Apr 26 00:17:09 2007  commencing relation filtering
Thu Apr 26 00:17:09 2007  commencing duplicate removal, pass 1
Thu Apr 26 00:17:11 2007  found 3182 hash collisions in 171299 relations
Thu Apr 26 00:17:11 2007  commencing duplicate removal, pass 2
Thu Apr 26 00:17:11 2007  found 3128 duplicates and 168171 unique relations
Thu Apr 26 00:17:11 2007  memory use: 36.1 MB
Thu Apr 26 00:17:12 2007  ignoring smallest 76059 rational and 75900 algebraic ideals
Thu Apr 26 00:17:12 2007  filtering rational ideals above 965961
Thu Apr 26 00:17:12 2007  filtering algebraic ideals above 965961
Thu Apr 26 00:17:12 2007  need 334309 more relations than ideals
Thu Apr 26 00:17:12 2007  commencing singleton removal, pass 1
Thu Apr 26 00:17:13 2007  relations with 0 large ideals: 7154
Thu Apr 26 00:17:13 2007  relations with 1 large ideals: 49999
Thu Apr 26 00:17:13 2007  relations with 2 large ideals: 87574
Thu Apr 26 00:17:13 2007  relations with 3 large ideals: 22952
Thu Apr 26 00:17:13 2007  relations with 4 large ideals: 492
Thu Apr 26 00:17:13 2007  relations with 5 large ideals: 0
Thu Apr 26 00:17:13 2007  relations with 6 large ideals: 0
Thu Apr 26 00:17:13 2007  relations with 7+ large ideals: 0
Thu Apr 26 00:17:13 2007  168171 relations and about 261711 large ideals
Thu Apr 26 00:17:13 2007  commencing singleton removal, pass 2
Thu Apr 26 00:17:15 2007  found 153478 singletons
Thu Apr 26 00:17:15 2007  current dataset: 14693 relations and about 7690 large ideals
Thu Apr 26 00:17:15 2007  commencing singleton removal, final pass
Thu Apr 26 00:17:15 2007  memory use: 9.1 MB
Thu Apr 26 00:17:15 2007  commencing in-memory singleton removal
Thu Apr 26 00:17:15 2007  begin with 14693 relations and 7734 unique ideals
Thu Apr 26 00:17:15 2007  reduce to 8938 relations and 939 ideals in 4 passes
Thu Apr 26 00:17:15 2007  max relations containing the same ideal: 3
Thu Apr 26 00:17:15 2007  not enough excess, attempting to create matrix anyway
Thu Apr 26 00:17:15 2007  filtering wants 978930 more relations
Thu Apr 26 00:17:15 2007  c126 factor: 407489615500169800857250950565976106355321189765537232596572514940677926345490888565626525440064766633254006824434321250360001
Thu Apr 26 00:17:15 2007  elapsed time 00:00:07

Only 171299 relations with 978930 more relations needed.

What happened to my other 900M relations?

What am i doing wrong?

[jasonp]

Originally Posted by smh

Only 171299 relations with 978930 more relations needed.

What happened to my other 900M relations?

What am i doing wrong?

The only thing I can think of is that the first character of most of the lines in your relation file is not a digit. Did the relation dump take place in unix/windows but the msieve run take place on windows/unix? The other possibility is that the file is truncated for some reason. If you have a 'wc' command, could you run 'wc <relation file>'? The first number it returns is the number of lines, and this should be about 1M

Also, the NFS square root will not work for this case because it assumes R1 will never be negative. I'll have to fix that for the next version, and stop being lazy about these things.

jasonp

[smh]

I tried again, this time will all relations GGNFS produced (enough to finish the factorization, but the output is exactly the same.

Originally Posted by jasonp

The only thing I can think of is that the first character of most of the lines in your relation file is not a digit. Did the relation dump take place in unix/windows but the msieve run take place on windows/unix?

I didn't dump the relations. I kept the relations by setting $SAVEPAIRS=1 in factlat.pl. All in windows (no cygwin, etc).

All lines exept the las few hundred look like:

1084042,474961:752ed5,259F,3CA7,13363,A5E89,17,71,1EB:840a91,5FE3,8A77,1C48D,3,25,C7,6DD89
412310,393517:1FA5,3EA1,118BB,83863,992B3,3,3,5,259,2F9:7508b,f30d3,1D5D,302BF,B,95,6DD89
1848322,1147639:310a03,179F,C803,C919,14AA9,4237F,17,7:e6e91,11C9B,19229,1C8D9,3,13,C5,7,7,6DD89
886352,276275:dd4fe9,8BF,1613,1D50D,2F447,13,2E3,2F9:106379,137B,18AD,186A3,3,11,293,5,B,6DD89
-186628,93787:1ced63f,210B9,6B96B,A29D9,3,3,B,97,35B:23323d,1369,181D,3FFD,5D1,6DD89
-69202,159267:ece3f,66746f,FD99,1FA6B,45EFB,EF,7:ab987b,2E9D,5195B,1CD,7,7,B,6DD89
388016,2803:813119,7577,18B99,18D8B,51091,3,3,3B:1271eb7,1DB3,1284D,B,B,8B,209,6DD89
791458,697849:4e5fb7,22481f,16BD,673F,D103,11,25,29,2F:832885,925,7D03,3,3,3,B,E9,223,371,6DD89
1535674,1102959:52a821,D79,1B31,BCF3,E279,C5,1E7,2E7,7:12d2071,166F,13,6D,101,151,1C9,257,7,7,6DD89

Originally Posted by jasonp

The other possibility is that the file is truncated for some reason. If you have a 'wc' command, could you run 'wc <relation file>'? The first number it returns is the number of lines, and this should be about 1M

Output of wc msieve.dat:
1500775 1500783 140995349 msieve.dat[QUOTE=jasonp;104632]

[fivemack]

Originally Posted by jasonp

Your number (by itself) must go into a file that is the argument of '-i', while the file that contains the polynomial should be the argument to '-nf'. Also, the relations file must have 'N <your number>' as its first line.

OK, when I do that it works, and I've successfully reprocessed a C108. I'm not entirely happy about appending the factor base to the input msieve.fb file - I suppose somehow I feel that input files should be read-only - but otherwise it's fine.

Originally Posted by jasonp

You will be in unknown territory trying to complete a 200-digit SNFS job. The largest NFS job that I've seen completed had 13.5 million relations. See this post for further details on modifying the source before trying. Do the relations have 64-bit 'a' values?
jasonp

Cool, unknown territory! The polynomial isn't skewed, so I suspect the relations will rarely have 64-bit 'a' values even though I've used gnfs-lasieve14; I guess it makes sense to assume a ~ 2^{sieve}*sqrt(qmax) in the unskewed case, which is safely below 2^31.

Should I anticipate issues with msieve.dat of over 2^31 bytes?

[jasonp]

Originally Posted by fivemack

Cool, unknown territory! The polynomial isn't skewed, so I suspect the relations will rarely have 64-bit 'a' values even though I've used gnfs-lasieve14; I guess it makes sense to assume a ~ 2^{sieve}*sqrt(qmax) in the unskewed case, which is safely below 2^31.

Should I anticipate issues with msieve.dat of over 2^31 bytes?

If the underlying filesystem supports it, then it shouldn't be an issue (the postprocessing only makes sequential passes through the relations, by design). For safety's sake I would run the postprocessing as separate passes though; the memory consumption at the end of the filtering and the beginning of the linear algebra will be the highest, and it will definitely get into the gigabytes.

[smh]

Originally Posted by jasonp

Sander, I don't know what could be going on; if you can get me the relations I'll get to the bottom of it, otherwise I'd suggest waiting for 1.20 and then taking this to email.

I won't be home until sunday night so it's hard to get you the relations right now.

It's no big deal anyway. This was just a test run. The number was factored with ggnfs anyway.

I'll try some other numbers next week.

[fivemack]

Note that, to handle numbers of more than 199 digits, not only should you remove the limit at line 340 of common/expr_eval.c and set MAX_MP_WORDS=32 in include/mp.h, but also change line 239 of demo.c to 'char buf[300]'; otherwise it truncates the number at 199 digits, which causes other than desirable results :errm:

The relations are stored on a RAID1 array of reasonable speed, but it still takes quite a while just to do the duplicate removal ... it ran for an hour, before saying

memory use: 1069.5 MB
commencing in-memory singleton removal
begin with 30309368 relations and 31644849 unique ideals
reduce to 7508529 relations and 4446570 ideals in 21 passes
max relations containing the same ideal: 12
not enough excess, attempting to create matrix anyway
filtering wants 24671685 more relations

When it says 'filtering wants N more relations', presumably that's N more relations added to msieve.dat (in which case, since I get about 120k relations per CPU-hour, that's both CPUs of kolmogorov running until Tuesday) rather than N more relations after filtering; it seems a very precise request!