Msieve 1.41 Feedback - Page 12

jasonp · 2009-05-23, 21:02

Quote:

Originally Posted by Andi47

Don't you have a possibility to chose fixed "random seeds" for bughunting? I don't have the relations anymore

If the problem is in the multiple-precision library, then it will depend on having all the same relations in the order in which they occurred in the savefile. Since you used the GGNFS lattice siever I can't guarantee being able to generate that by myself.

I'm not inclined to worry about it much; there are other things that need fixing more.

frmky · 2009-05-27, 17:38

The filtering of the complete data set for 2,908+ failed. The log is attached. At this point, though, I wouldn't worry about it since Tom has taught us that with proper selection of parameters, many fewer relations are sufficient.

jasonp · 2009-05-27, 18:18

Quote:

Originally Posted by frmky

The filtering of the complete data set for 2,908+ failed. The log is attached. At this point, though, I wouldn't worry about it since Tom has taught us that with proper selection of parameters, many fewer relations are sufficient.

The heavy relation code worked as expected, but the filtering was not shown enough ideals to produce a correct size matrix in the first place (a matrix of size 32M is just yucky). Clearly just deleting relations is not going to thin out the dataset so that the merge can run immediately; at the least you need to rerun the clique processing. But it's possible that nothing will work in this situation unless you know about almost all the ideals, not just those with low weight.

Batalov · 2009-05-29, 03:15

A curious case with square root modulo 53 (yes, simply 53!) happened while factoring 6,672M, the last Cunningham table number with difficulty less than 200:

Code:

Thu May 28 19:21:26 2009  multiplying 5583346 relations
Thu May 28 19:25:59 2009  multiply complete, coefficients have about 161.97 million bits
Thu May 28 19:26:01 2009  warning: no irreducible prime found, switching to small primes
Thu May 28 19:26:04 2009  initial square root is modulo 53
Thu May 28 19:37:15 2009  sqrtTime: 1052
Thu May 28 19:37:15 2009  prp78 factor: 797755198398378136992989897173778551819524893213077735137125857196400787268209
Thu May 28 19:37:15 2009  prp82 factor: 5537679016126244829242773647897792916417225946706147891702969058169485639839312841
Thu May 28 19:37:15 2009  elapsed time 00:17:34

The log and details are in the Cunningham 6+ thread.

jasonp · 2009-05-29, 13:32

This explanation will be a little long-winded:

The algebraic square root needs to pretend each relation is a degree-1 polynomial. Then multiply all the relations together modulo the algebraic poly F, yielding a polynomial R with huge coefficients. Then find a square root of R (i.e. a polynomial that equals R when squared modulo F). The latter is done via p-adic Newton iteration: choose a small prime p and find the square root of R mod p somehow, then run Newton iteration k times to make the square root work mod p^k. When p^k is larger than the coefficients of the square root polynomial, then you will have the square root required. Per Leslie Jensen showed this worked well for small factorizations, but msieve was the first code that showed the algorithm was practical for industrial-size factorizations; I had no idea if it would be fast enough when I was writing it.

The only requirement for p above is that F is irreducible mod p. When that's true, the square root algorithm is guaranteed to work and there's a clever way to find the square root of R mod p. Unfortunately, a few degree-4 and degree-6 F polynomials are not irreducible modulo any prime p, so the clever algorithm for the initial square root will not work and the complete algebraic square root may not work either. When that happens, the code chooses a small p for which F mod p has no *linear* polynomial factors (this is easy to check) and finds the initial square root polynomial by brute force, trying all polynomials with coefficients between 0 and p-1 until it finds one that equals R mod p when squared modulo F mod p. Because this is expensive, p is chosen as the first prime above 50 that will work (not the customary 6-10 digit value the code ordinarily chooses). You can make p smaller, but that increases the chance that the Newton iteration will fail.

Newton failure happens when the two square roots of (R mod p) mod (F mod p) happen to coincide. This is impossible when F is irreducible mod p, but for general p it can happen and it becomes more likely when p becomes smaller, since there are fewer polynomials to choose from. Experience shows that with this choice of p the Newton iteration fails about half the time, so on average you need about twice as many dependencies to finish the factorization.

A surprising number of XYYXF numbers have degree-4 SNFS polynomials where this mess is necessary. To date I think only one degree-6 job (a monster by Greg) has needed the special-case p.

mklasson · 2009-06-09, 10:33

Just had a weird little error with msieve 1.41 and factMsieve.pl with NUM_CPUS=2:

Code:

Tue Jun 09 06:49:53 2009  Msieve v. 1.41
Tue Jun 09 06:49:53 2009  random seeds: cf59a860 97b0d595
Tue Jun 09 06:49:53 2009  factoring 2378863810492383364784724016929764517542240407863155206841742219996638335582297762782527116002786833789317163196667710293879 (124 digits)
Tue Jun 09 06:49:54 2009  searching for 15-digit factors
Tue Jun 09 06:49:54 2009  ECM stage 1 factor found
Tue Jun 09 06:49:54 2009  ECM stage 1 factor found
Tue Jun 09 06:49:54 2009  ECM stage 1 factor found
Tue Jun 09 06:49:54 2009  commencing number field sieve (124-digit input)
Tue Jun 09 06:49:54 2009  R0: -681346488621441544095199
Tue Jun 09 06:49:54 2009  R1:  34093445133979
Tue Jun 09 06:49:54 2009  A0: -166525874832126379938206323680
Tue Jun 09 06:49:54 2009  A1:  10947187180220372892784692
Tue Jun 09 06:49:54 2009  A2:  56968751045950668526
Tue Jun 09 06:49:54 2009  A3: -1664642868411548
Tue Jun 09 06:49:54 2009  A4:  10775598711
Tue Jun 09 06:49:54 2009  A5:  16200
Tue Jun 09 06:49:54 2009  skew 136315.64, size 8.633867e-012, alpha -6.832790, combined = 2.027516e-010
Tue Jun 09 06:49:54 2009  
Tue Jun 09 06:49:54 2009  commencing relation filtering
Tue Jun 09 06:49:54 2009  commencing duplicate removal, pass 1
Tue Jun 09 06:50:31 2009  found 734509 hash collisions in 8925897 relations
Tue Jun 09 06:50:47 2009  added 184 free relations
Tue Jun 09 06:50:47 2009  commencing duplicate removal, pass 2
Tue Jun 09 06:50:52 2009  found 646138 duplicates and 8279943 unique relations
Tue Jun 09 06:50:52 2009  memory use: 48.6 MB
Tue Jun 09 06:50:52 2009  reading rational ideals above 4653056
Tue Jun 09 06:50:52 2009  reading algebraic ideals above 4653056
Tue Jun 09 06:50:52 2009  commencing singleton removal, pass 1
Tue Jun 09 06:51:29 2009  relations with 0 large ideals: 102572
Tue Jun 09 06:51:29 2009  relations with 1 large ideals: 758670
Tue Jun 09 06:51:29 2009  relations with 2 large ideals: 2327601
Tue Jun 09 06:51:29 2009  relations with 3 large ideals: 3207157
Tue Jun 09 06:51:29 2009  relations with 4 large ideals: 1744235
Tue Jun 09 06:51:29 2009  relations with 5 large ideals: 78614
Tue Jun 09 06:51:29 2009  relations with 6 large ideals: 61092
Tue Jun 09 06:51:29 2009  relations with 7+ large ideals: 2
Tue Jun 09 06:51:29 2009  8279943 relations and about 9184006 large ideals
Tue Jun 09 06:51:29 2009  commencing singleton removal, pass 2
Tue Jun 09 06:52:29 2009  found 3935349 singletons
Tue Jun 09 06:52:29 2009  current dataset: 4344594 relations and about 4199819 large ideals
Tue Jun 09 06:52:29 2009  error: singleton2 can't rename output file
(and in the console:) Return value 65280. Terminating...

It had been running successfully for quite a while, gathering ~1GB relations.

Any idea what went wrong?

10metreh · 2009-06-09, 11:54

Quote:

Originally Posted by mklasson

<snip>

Retry with 1.42, see if it makes any difference.

mklasson · 2009-06-09, 12:03

Quote:

Originally Posted by 10metreh

Retry with 1.42, see if it makes any difference.

Well, just trying again with 1.41 worked too. Still though, would be nice if it was a bug that could be squashed.

jasonp · 2009-06-09, 15:48

Are you low on disk space at all? Another possibility is that the destination file was deleted just before the file in question was renamed; maybe the delete took a little too long the first time and windows had locked the file while the rename was attempted. The files in question are quite small (the library never copies the relation file itself).

mklasson · 2009-06-09, 16:01

Quote:

Originally Posted by jasonp

Are you low on disk space at all? Another possibility is that the destination file was deleted just before the file in question was renamed; maybe the delete took a little too long the first time and windows had locked the file while the rename was attempted. The files in question are quite small (the library never copies the relation file itself).

Nope, 100+ GB free. The disk could very well have been working hard as I'm running four aliqueits (and hence possibly msieves) in parallel, but I've been doing that for several months now.

Surely any file deletion should be completed before windows passes control back to msieve, no? For what it's worth there was a ~15MB test.dat.1(sp?) alongside the ~1GB test.dat in the dir after the failure. Ah well...

EDIT: I just noticed my system acting a little weird overall now, so maybe this was all down to some other program going nuts.

2009-05-29, 13:32	#126
jasonp Tribal Bullet Oct 2004 6725₈ Posts	This explanation will be a little long-winded: The algebraic square root needs to pretend each relation is a degree-1 polynomial. Then multiply all the relations together modulo the algebraic poly F, yielding a polynomial R with huge coefficients. Then find a square root of R (i.e. a polynomial that equals R when squared modulo F). The latter is done via p-adic Newton iteration: choose a small prime p and find the square root of R mod p somehow, then run Newton iteration k times to make the square root work mod p^k. When p^k is larger than the coefficients of the square root polynomial, then you will have the square root required. Per Leslie Jensen showed this worked well for small factorizations, but msieve was the first code that showed the algorithm was practical for industrial-size factorizations; I had no idea if it would be fast enough when I was writing it. The only requirement for p above is that F is irreducible mod p. When that's true, the square root algorithm is guaranteed to work and there's a clever way to find the square root of R mod p. Unfortunately, a few degree-4 and degree-6 F polynomials are not irreducible modulo any prime p, so the clever algorithm for the initial square root will not work and the complete algebraic square root may not work either. When that happens, the code chooses a small p for which F mod p has no linear polynomial factors (this is easy to check) and finds the initial square root polynomial by brute force, trying all polynomials with coefficients between 0 and p-1 until it finds one that equals R mod p when squared modulo F mod p. Because this is expensive, p is chosen as the first prime above 50 that will work (not the customary 6-10 digit value the code ordinarily chooses). You can make p smaller, but that increases the chance that the Newton iteration will fail. Newton failure happens when the two square roots of (R mod p) mod (F mod p) happen to coincide. This is impossible when F is irreducible mod p, but for general p it can happen and it becomes more likely when p becomes smaller, since there are fewer polynomials to choose from. Experience shows that with this choice of p the Newton iteration fails about half the time, so on average you need about twice as many dependencies to finish the factorization. A surprising number of XYYXF numbers have degree-4 SNFS polynomials where this mess is necessary. To date I think only one degree-6 job (a monster by Greg) has needed the special-case p. Last fiddled with by jasonp on 2009-05-29 at 15:05 Reason: p^k doesn't have to be as large as R, only the square root

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.50 feedback	firejuggler	Msieve	99	2013-02-17 11:53
Msieve v1.48 feedback	Jeff Gilchrist	Msieve	48	2011-06-10 18:18
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53
Msieve 1.42 feedback	Andi47	Msieve	167	2009-10-18 19:37

2009-06-09, 15:48	#130
jasonp Tribal Bullet Oct 2004 6725₈ Posts	Are you low on disk space at all? Another possibility is that the destination file was deleted just before the file in question was renamed; maybe the delete took a little too long the first time and windows had locked the file while the rename was attempted. The files in question are quite small (the library never copies the relation file itself).