Msieve 1.53 feedback - Page 9

Dubslow · 2015-12-18, 02:14

Quote:

Originally Posted by jyb

I see this happen occasionally, but msieve just moves on to the next dependency, so it's not really a big problem. Did that not happen here?

It did, but I've not seen it before. Is it perhaps a bug, or is it just a 1/1000 chance for any given job?

I saved the data for posterity if it's the former.

jasonp · 2015-12-18, 16:54

The newton iteration in the square root converges only with high probability. The linear algebra adds 20 quadratic characters, which is supposed to mean there's only a 1-in-a-million chance that the LA works correctly but the square root does not. I don't flatter myself into thinking the number of dependencies everyone tries is that large, though.

chris2be8 · 2015-12-18, 16:55

It's fairly common for SNFS jobs to do this, about 0.5% of my SNFS jobs get it. But I've not seen it for a GNFS job.

If you get the "warning: no irreducible prime found, switching to small primes" message it will probably happen several times in that job. But can also happen without that.

Chris

Edit: Cross posted with jasonp.

Alfred · 2016-01-30, 23:19

Hello,

factoring 2011^69-1, msieve succeeded, but I was surprised at the line

Quote:

Sat Jan 30 23:16:58 2016 warning: no irreducible prime found, switching to small primes

in the log file.

Causes my (stupid?) snfs poly this line?

Alfred

jasonp · 2016-01-31, 14:00

This isn't an error, just a property of the specific polynomial. It makes the square root a little harder but is not fatal.

VictordeHolland · 2016-02-26, 20:27

Everything seemed to work fine, untill the part I marked with bold (in-memory Singleton removal):

Code:

Mon Feb 22 22:33:12 2016  
Mon Feb 22 22:33:12 2016  
Mon Feb 22 22:33:12 2016  Msieve v. 1.53 (SVN 988)
Mon Feb 22 22:33:12 2016  random seeds: 8f9d9280 5f795880
Mon Feb 22 22:33:12 2016  factoring 4439397308060887643973342113399178207289534521567468479007341740378343472786431623680647410832199479340278911399740887735300185093750643499869968204585762181943724831 (166 digits)
Mon Feb 22 22:33:13 2016  searching for 15-digit factors
Mon Feb 22 22:33:13 2016  commencing number field sieve (166-digit input)
Mon Feb 22 22:33:13 2016  R0: -50999664317994704147101972769517
Mon Feb 22 22:33:13 2016  R1: 355904783004733
Mon Feb 22 22:33:13 2016  A0: -13443855893951418600468425813845928300
Mon Feb 22 22:33:13 2016  A1: 34961899444543208769262669905430
Mon Feb 22 22:33:13 2016  A2: 643382862800113977007891622
Mon Feb 22 22:33:13 2016  A3: 654506450741125318754
Mon Feb 22 22:33:13 2016  A4: -281899531995771
Mon Feb 22 22:33:13 2016  A5: 12867300
Mon Feb 22 22:33:13 2016  skew 1.00, size 3.516e-016, alpha -7.031, combined = 8.288e-015 rroots = 5
Mon Feb 22 22:33:13 2016  
Mon Feb 22 22:33:13 2016  commencing relation filtering
Mon Feb 22 22:33:13 2016  setting target matrix density to 120.0
Mon Feb 22 22:33:13 2016  estimated available RAM is 16331.2 MB
Mon Feb 22 22:33:13 2016  commencing duplicate removal, pass 1

<errors reading relations>

Mon Feb 22 23:05:07 2016  skipped 86 relations with composite factors
Mon Feb 22 23:05:07 2016  found 41784425 hash collisions in 223174775 relations
Mon Feb 22 23:05:35 2016  added 122046 free relations
Mon Feb 22 23:05:35 2016  commencing duplicate removal, pass 2
Mon Feb 22 23:07:30 2016  found 40915338 duplicates and 182381483 unique relations
Mon Feb 22 23:07:30 2016  memory use: 1321.5 MB
Mon Feb 22 23:07:30 2016  reading ideals above 200605696
Mon Feb 22 23:07:30 2016  commencing singleton removal, initial pass
Mon Feb 22 23:28:02 2016  memory use: 3012.0 MB
Mon Feb 22 23:28:02 2016  reading all ideals from disk
Mon Feb 22 23:28:10 2016  memory use: 2803.5 MB
Mon Feb 22 23:28:15 2016  keeping 143232241 ideals with weight <= 200, target excess is 22588673
Mon Feb 22 23:28:20 2016  commencing in-memory singleton removal
Mon Feb 22 23:28:24 2016  begin with 182381483 relations and 143232241 unique ideals
Mon Feb 22 23:29:14 2016  reduce to 112617367 relations and 65539142 ideals in 14 passes
Mon Feb 22 23:29:14 2016  max relations containing the same ideal: 30
Mon Feb 22 23:29:20 2016  reading ideals above 720000
Mon Feb 22 23:29:20 2016  commencing singleton removal, initial pass
Mon Feb 22 23:43:55 2016  memory use: 2756.0 MB
Mon Feb 22 23:43:56 2016  reading all ideals from disk
Mon Feb 22 23:43:56 2016  memory use: 4349.8 MB
Mon Feb 22 23:43:57 2016  keeping 21816557 ideals with weight <= 200, target excess is 65936804
Mon Feb 22 23:43:58 2016  commencing in-memory singleton removal
Mon Feb 22 23:43:59 2016  begin with 112617367 relations and 21816557 unique ideals
Mon Feb 22 23:44:00 2016  reduce to 105986927 relations and 0 ideals in 4 passes
Mon Feb 22 23:44:00 2016  max relations containing the same ideal: 0
Mon Feb 22 23:44:02 2016  relations with 0 large ideals: 105986927
Mon Feb 22 23:44:02 2016  relations with 1 large ideals: 0
Mon Feb 22 23:44:02 2016  relations with 2 large ideals: 0
Mon Feb 22 23:44:02 2016  relations with 3 large ideals: 0
Mon Feb 22 23:44:02 2016  relations with 4 large ideals: 0
Mon Feb 22 23:44:02 2016  relations with 5 large ideals: 0
Mon Feb 22 23:44:02 2016  relations with 6 large ideals: 0
Mon Feb 22 23:44:02 2016  relations with 7+ large ideals: 0
Mon Feb 22 23:44:02 2016  commencing 2-way merge
Mon Feb 22 23:44:09 2016  reduce to 105986927 relation sets and 0 unique ideals
Mon Feb 22 23:44:09 2016  commencing full merge
Mon Feb 22 23:44:10 2016  memory use: 2021.5 MB
Mon Feb 22 23:44:16 2016  found 105986927 cycles, need 65937004
Mon Feb 22 23:44:17 2016  weight of 65937004 cycles is about 0 (0.00/cycle)
Mon Feb 22 23:44:17 2016  distribution of cycle lengths:
Mon Feb 22 23:44:17 2016  1 relations: 65937004
Mon Feb 22 23:44:17 2016  2 relations: 0
Mon Feb 22 23:44:17 2016  3 relations: 0
Mon Feb 22 23:44:17 2016  4 relations: 0
Mon Feb 22 23:44:17 2016  5 relations: 0
Mon Feb 22 23:44:17 2016  6 relations: 0
Mon Feb 22 23:44:17 2016  7 relations: 0
Mon Feb 22 23:44:17 2016  8 relations: 0
Mon Feb 22 23:44:17 2016  9 relations: 0
Mon Feb 22 23:44:17 2016  10+ relations: 0
Mon Feb 22 23:44:17 2016  heaviest cycle: 1 relations
Mon Feb 22 23:44:17 2016  commencing cycle optimization
Mon Feb 22 23:44:17 2016  start with 65937004 relations
Mon Feb 22 23:44:17 2016  pruned 0 relations
Mon Feb 22 23:44:17 2016  memory use: 1257.6 MB
Mon Feb 22 23:44:17 2016  distribution of cycle lengths:
Mon Feb 22 23:44:17 2016  1 relations: 65937004
Mon Feb 22 23:44:17 2016  2 relations: 0
Mon Feb 22 23:44:17 2016  3 relations: 0
Mon Feb 22 23:44:17 2016  4 relations: 0
Mon Feb 22 23:44:17 2016  5 relations: 0
Mon Feb 22 23:44:17 2016  6 relations: 0
Mon Feb 22 23:44:17 2016  7 relations: 0
Mon Feb 22 23:44:17 2016  8 relations: 0
Mon Feb 22 23:44:17 2016  9 relations: 0
Mon Feb 22 23:44:17 2016  10+ relations: 0
Mon Feb 22 23:44:17 2016  heaviest cycle: 1 relations
Mon Feb 22 23:44:24 2016  RelProcTime: 4271
Mon Feb 22 23:44:24 2016  elapsed time 01:11:12
Wed Feb 24 00:32:03 2016  
Wed Feb 24 00:32:03 2016  
Wed Feb 24 00:32:03 2016  Msieve v. 1.53 (SVN 988)
Wed Feb 24 00:32:03 2016  random seeds: 502b727c fe08a9ec
Wed Feb 24 00:32:03 2016  factoring 4439397308060887643973342113399178207289534521567468479007341740378343472786431623680647410832199479340278911399740887735300185093750643499869968204585762181943724831 (166 digits)
Wed Feb 24 00:32:04 2016  searching for 15-digit factors
Wed Feb 24 00:32:04 2016  commencing number field sieve (166-digit input)
Wed Feb 24 00:32:04 2016  R0: -50999664317994704147101972769517
Wed Feb 24 00:32:04 2016  R1: 355904783004733
Wed Feb 24 00:32:04 2016  A0: -13443855893951418600468425813845928300
Wed Feb 24 00:32:04 2016  A1: 34961899444543208769262669905430
Wed Feb 24 00:32:04 2016  A2: 643382862800113977007891622
Wed Feb 24 00:32:04 2016  A3: 654506450741125318754
Wed Feb 24 00:32:04 2016  A4: -281899531995771
Wed Feb 24 00:32:04 2016  A5: 12867300
Wed Feb 24 00:32:04 2016  skew 1.00, size 3.516e-016, alpha -7.031, combined = 8.288e-015 rroots = 5
Wed Feb 24 00:32:04 2016  
Wed Feb 24 00:32:04 2016  commencing linear algebra
Wed Feb 24 00:32:04 2016  read 323 cycles
Wed Feb 24 00:32:04 2016  cycles contain 1 unique relations
Wed Feb 24 00:32:05 2016  read 1 relations
Wed Feb 24 00:32:05 2016  using 20 quadratic characters above 4294917295
Wed Feb 24 00:32:05 2016  building initial matrix
Wed Feb 24 00:32:05 2016  memory use: 0.2 MB
Wed Feb 24 00:32:05 2016  read 323 cycles
Wed Feb 24 00:32:05 2016  matrix is 123 x 323 (0.0 MB) with weight 10982 (34.00/col)
Wed Feb 24 00:32:05 2016  sparse part has weight 5168 (16.00/col)
Wed Feb 24 00:32:05 2016  filtering completed in 1 passes
Wed Feb 24 00:32:05 2016  matrix is 123 x 323 (0.0 MB) with weight 10982 (34.00/col)
Wed Feb 24 00:32:05 2016  sparse part has weight 5168 (16.00/col)
Wed Feb 24 00:32:05 2016  matrix starts at (0, 0)
Wed Feb 24 00:32:05 2016  matrix is 123 x 323 (0.0 MB) with weight 10982 (34.00/col)
Wed Feb 24 00:32:05 2016  sparse part has weight 5168 (16.00/col)
Wed Feb 24 00:32:05 2016  matrix includes 107 packed rows
Wed Feb 24 00:32:05 2016  commencing Lanczos iteration
Wed Feb 24 00:32:05 2016  memory use: 0.0 MB
Wed Feb 24 00:32:05 2016  lanczos halted after 1 iterations (dim = 0)
Wed Feb 24 00:32:05 2016  linear algebra failed; retrying...

Is in-memory singleton removal broken in SVN 988, or is my binary/setup broken? (I used the one compiled for Sandybridge by ATH from this post: http://mersenneforum.org/showpost.ph...5&postcount=34 )

SVN 946 works fine on the same job and ends with a normal sized matrix.

Code:

Thu Feb 25 01:31:08 2016  found 9113299 cycles, need 9050763
Thu Feb 25 01:31:09 2016  weight of 9050763 cycles is about 1086930695 (120.09/cycle)
Thu Feb 25 01:31:09 2016  distribution of cycle lengths:
Thu Feb 25 01:31:09 2016  1 relations: 136620
Thu Feb 25 01:31:09 2016  2 relations: 424185
Thu Feb 25 01:31:09 2016  3 relations: 583032
Thu Feb 25 01:31:09 2016  4 relations: 672696
Thu Feb 25 01:31:09 2016  5 relations: 749013
Thu Feb 25 01:31:09 2016  6 relations: 772416
Thu Feb 25 01:31:09 2016  7 relations: 769070
Thu Feb 25 01:31:09 2016  8 relations: 736445
Thu Feb 25 01:31:09 2016  9 relations: 683918
Thu Feb 25 01:31:09 2016  10+ relations: 3523368
Thu Feb 25 01:31:09 2016  heaviest cycle: 28 relations
Thu Feb 25 01:31:10 2016  commencing cycle optimization
Thu Feb 25 01:31:25 2016  start with 79534348 relations
Thu Feb 25 01:34:28 2016  pruned 4485793 relations
Thu Feb 25 01:34:28 2016  memory use: 2034.9 MB
Thu Feb 25 01:34:28 2016  distribution of cycle lengths:
Thu Feb 25 01:34:28 2016  1 relations: 136620
Thu Feb 25 01:34:28 2016  2 relations: 438468
Thu Feb 25 01:34:28 2016  3 relations: 613174
Thu Feb 25 01:34:28 2016  4 relations: 711752
Thu Feb 25 01:34:28 2016  5 relations: 801037
Thu Feb 25 01:34:28 2016  6 relations: 827028
Thu Feb 25 01:34:28 2016  7 relations: 826511
Thu Feb 25 01:34:28 2016  8 relations: 785450
Thu Feb 25 01:34:28 2016  9 relations: 724154
Thu Feb 25 01:34:28 2016  10+ relations: 3186569
Thu Feb 25 01:34:28 2016  heaviest cycle: 27 relations
Thu Feb 25 01:34:41 2016  RelProcTime: 6717
Thu Feb 25 01:34:41 2016  elapsed time 01:51:58

jasonp · 2016-02-27, 17:52

If the older version had not worked, I would have said you have way too many excess relations such that almost all ideals were singletons.

Does the more recent version work if you start with perhaps 2/3 of the original dataset? There's an option you can add to the filtering that will specify the number of starting relations.

Alfred · 2016-03-21, 15:25

Usually msieve seriously needs 1000000 more relations ...
but sometimes it joky needs 1088046 more relations ??

Code:

Mon Mar 21 14:20:14 2016  
Mon Mar 21 14:20:15 2016  
Mon Mar 21 14:20:15 2016  Msieve v. 1.53 (SVN unknown)
Mon Mar 21 14:20:15 2016  random seeds: 016cfa78 3afd6aad
Mon Mar 21 14:20:15 2016  factoring 946958298080857636136138548088793634519831001191049984260982557287795889693531589433834562546638553033316541513265050391733507032329398090527842107614526200758649 (162 digits)
Mon Mar 21 14:20:17 2016  no P-1/P+1/ECM available, skipping
Mon Mar 21 14:20:17 2016  commencing number field sieve (162-digit input)
Mon Mar 21 14:20:17 2016  R0: -91958881684291388898886827645958
Mon Mar 21 14:20:17 2016  R1: 20768521811363279
Mon Mar 21 14:20:17 2016  A0: -87551436592502930318092533374234785554081
Mon Mar 21 14:20:17 2016  A1: -128267673751264048086034011499966312
Mon Mar 21 14:20:17 2016  A2: 3823244302971200959519265566
Mon Mar 21 14:20:17 2016  A3: 13566627676314435288
Mon Mar 21 14:20:17 2016  A4: -64315942845
Mon Mar 21 14:20:17 2016  A5: 144
Mon Mar 21 14:20:17 2016  skew 151715519.70, size 9.359e-016, alpha -8.066, combined = 1.093e-012 rroots = 3
Mon Mar 21 14:20:17 2016  
Mon Mar 21 14:20:18 2016  commencing relation filtering
Mon Mar 21 14:20:18 2016  estimated available RAM is 24567.3 MB
Mon Mar 21 14:20:18 2016  commencing duplicate removal, pass 1
Mon Mar 21 14:41:43 2016  skipped 9 relations with composite factors
Mon Mar 21 14:41:43 2016  found 7897487 hash collisions in 63998047 relations
Mon Mar 21 14:42:55 2016  added 6279 free relations
Mon Mar 21 14:42:55 2016  commencing duplicate removal, pass 2
Mon Mar 21 14:44:12 2016  found 5720806 duplicates and 58283520 unique relations
Mon Mar 21 14:44:13 2016  memory use: 330.4 MB
Mon Mar 21 14:44:13 2016  reading ideals above 720000
Mon Mar 21 14:44:13 2016  commencing singleton removal, initial pass
Mon Mar 21 15:04:14 2016  memory use: 1506.0 MB
Mon Mar 21 15:04:15 2016  reading all ideals from disk
Mon Mar 21 15:04:19 2016  memory use: 2193.3 MB
Mon Mar 21 15:04:41 2016  keeping 73638961 ideals with weight <= 200, target excess is 313493
Mon Mar 21 15:04:55 2016  commencing in-memory singleton removal
Mon Mar 21 15:05:18 2016  begin with 58283519 relations and 73638961 unique ideals
Mon Mar 21 15:06:16 2016  reduce to 969 relations and 0 ideals in 15 passes
Mon Mar 21 15:06:16 2016  max relations containing the same ideal: 0
Mon Mar 21 15:06:16 2016  filtering wants 1088046 more relations
Mon Mar 21 15:06:17 2016  elapsed time 00:46:02

Maybe it is the correct answer of msieve to my invoking of msieve with obviously too few relations.

Alfred

Alfred · 2016-06-07, 20:06

I'm not able to factor the c143 from aliquot sequence 12012:2432.

After collecting 105.621.483 unique relations,
I started msieve, but it failed to build the initial matrix.

Code:

Mon Jun 06 13:18:17 2016  commencing linear algebra
Mon Jun 06 13:18:18 2016  read 4951153 cycles
Mon Jun 06 13:18:25 2016  cycles contain 17923131 unique relations
Mon Jun 06 13:21:15 2016  read 17923131 relations
Mon Jun 06 13:21:34 2016  using 20 quadratic characters above 2147482922
Mon Jun 06 13:22:46 2016  building initial matrix
Mon Jun 06 13:24:55 2016  memory use: 2226.2 MB
Mon Jun 06 13:25:08 2016  read 4951153 cycles
Mon Jun 06 13:25:10 2016  matrix is 4950974 x 4951153 (1498.0 MB) with weight 464089706 (93.73/col)
Mon Jun 06 13:25:10 2016  sparse part has weight 338215983 (68.31/col)
Mon Jun 06 13:25:50 2016  filtering completed in 2 passes
Mon Jun 06 13:25:52 2016  matrix is 4945245 x 4899932 (1495.6 MB) with weight 463849505 (94.66/col)
Mon Jun 06 13:25:52 2016  sparse part has weight 338157030 (69.01/col)
Mon Jun 06 13:26:12 2016  matrix starts at (0, 0)
Mon Jun 06 13:26:13 2016  matrix is 4945245 x 4899932 (1495.6 MB) with weight 463849505 (94.66/col)
Mon Jun 06 13:26:13 2016  sparse part has weight 338157030 (69.01/col)
Mon Jun 06 13:26:13 2016  matrix needs more columns than rows; try adding 2-3% more relations

So I collected a few more relations.
At the moment, I have 140.968.544 unique relations.
msieve still failes to build the matrix.

Code:

Tue Jun 07 20:18:20 2016  commencing linear algebra
Tue Jun 07 20:18:20 2016  read 2539447 cycles
Tue Jun 07 20:18:24 2016  cycles contain 7753533 unique relations
Tue Jun 07 20:21:42 2016  read 7753533 relations
Tue Jun 07 20:21:56 2016  using 20 quadratic characters above 2147482082
Tue Jun 07 20:22:37 2016  building initial matrix
Tue Jun 07 20:24:11 2016  memory use: 1002.0 MB
Tue Jun 07 20:24:18 2016  read 2539447 cycles
Tue Jun 07 20:24:19 2016  matrix is 2539257 x 2539447 (761.8 MB) with weight 238308145 (93.84/col)
Tue Jun 07 20:24:19 2016  sparse part has weight 171765028 (67.64/col)
Tue Jun 07 20:24:45 2016  filtering completed in 2 passes
Tue Jun 07 20:24:46 2016  matrix is 2538030 x 2514959 (760.7 MB) with weight 238257048 (94.74/col)
Tue Jun 07 20:24:46 2016  sparse part has weight 171746501 (68.29/col)
Tue Jun 07 20:25:21 2016  matrix starts at (0, 0)
Tue Jun 07 20:25:22 2016  matrix is 2538030 x 2514959 (760.7 MB) with weight 238257048 (94.74/col)
Tue Jun 07 20:25:22 2016  sparse part has weight 171746501 (68.29/col)
Tue Jun 07 20:25:22 2016  matrix needs more columns than rows; try adding 2-3% more relations

The complete log file is attached.
Maybe anyone has an idea?

The command line is (as usual?)

Code:

msieve -i 0.ini -s 0.out -l 0.log -nf 0.fb -t 8 -nc

I'd be very thankful for any help.

pinhodecarlos · 2016-06-07, 20:10

What's de default target_density your are using?

Alfred · 2016-06-07, 20:16

I did not append any "target_density=", so I think msieve uses TD=70 ?

2015-12-18, 16:55	#91
chris2be8 Sep 2009 2×1,039 Posts	It's fairly common for SNFS jobs to do this, about 0.5% of my SNFS jobs get it. But I've not seen it for a GNFS job. If you get the "warning: no irreducible prime found, switching to small primes" message it will probably happen several times in that job. But can also happen without that. Chris Edit: Cross posted with jasonp. Last fiddled with by chris2be8 on 2015-12-18 at 16:59 Reason: cross post.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
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
Msieve 1.41 Feedback	Batalov	Msieve	130	2009-06-09 16:01

2015-12-18, 16:54	#90
jasonp Tribal Bullet Oct 2004 3,541 Posts	The newton iteration in the square root converges only with high probability. The linear algebra adds 20 quadratic characters, which is supposed to mean there's only a 1-in-a-million chance that the LA works correctly but the square root does not. I don't flatter myself into thinking the number of dependencies everyone tries is that large, though.

2016-01-31, 14:00	#93
jasonp Tribal Bullet Oct 2004 3,541 Posts	This isn't an error, just a property of the specific polynomial. It makes the square root a little harder but is not fatal.

2016-02-27, 17:52	#95
jasonp Tribal Bullet Oct 2004 3541₁₀ Posts	If the older version had not worked, I would have said you have way too many excess relations such that almost all ideals were singletons. Does the more recent version work if you start with perhaps 2/3 of the original dataset? There's an option you can add to the filtering that will specify the number of starting relations.

2016-06-07, 20:10	#98
pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 3×17×97 Posts	What's de default target_density your are using?

2016-06-07, 20:16	#99
Alfred May 2013 Germany 5·17 Posts	I did not append any "target_density=", so I think msieve uses TD=70 ?