Msieve 1.41 Feedback - Page 8

mklasson · 2009-04-27, 15:56

Quote:

Originally Posted by akruppa

Hard to tell what's happening. It's impossible that three sigma were chosen by chance so that the order of the curve was smooth for both factors (but never for only one of them). Mklasson, is this error reproducible? If yes, maybe we can add some diagnotic output to msieve's smallfact/the GMP-ECM code. And which version of GMP-ECM and which cpu type do you use?

Yes, entirely reproducible. In fact, it seems to happen for any input number using Jeff's compiled msieve v1.41 binaries (both 32 and 64-bit). I just tried a few "msieve -v -np n" with a couple of different hard 80+ digit numbers and was always rewarded with

Code:

ECM stage 1 factor found
ECM stage 1 factor found
ECM stage 1 factor found

Jason's 32-bit binary works normally.

edit: oh, and my cpu is an i7. I'll let Jeff tell you about the gmp-ecm version. :)

Jeff Gilchrist · 2009-04-27, 16:07

Quote:

Originally Posted by mklasson

Yes, entirely reproducible. In fact, it seems to happen for any input number using Jeff's compiled msieve v1.41 binaries (both 32 and 64-bit). I just tried a few "msieve -v -np n" with a couple of different hard 80+ digit numbers and was always rewarded with

edit: oh, and my cpu is an i7. I'll let Jeff tell you about the gmp-ecm version. :)

Ah, that is probably why I have seen it.

I think it would be gmp-ecm 6.2.1 or 6.2.2. I can try building with 6.2.3 and see if it still does it.

Jeff Gilchrist · 2009-04-27, 16:16

Ok so I just re-compiled 1.41 with GMP-ECM 6.2.3 and also MPIR 1.1.1 and now the message goes away. I can reproduce the messages as well on my machine but with the new build they are not there.

Tonight when I get the chance I will update my website with new builds. So did something change in GMP-ECM 6.2.3 that might have fixed this? Didn't someone say that the interface to GMP-ECM changed slightly, could that be the issue? I might have been using SVN for the last build but this one is the tarball posted on the GMP-ECM site.

Jeff.

jasonp · 2009-04-27, 16:32

The function prototypes for the top-level calls to P+-1 and ECM in GMP-ECM have had an extra argument added after v6.2.2 was released, and unfortunately msieve uses these calls and not the supported GMP-ECM interface (next release will definitely change that).

Not sure if that's the problem here. I can see it being the issue if you use an old ecm.h but a new precompiled GMP-ECM lib...

akruppa · 2009-04-27, 17:29

Quote:

Originally Posted by Jeff Gilchrist

I might have been using SVN for the last build but this one is the tarball posted on the GMP-ECM site.

Jeff.

That would probably be the issue: the parameter list for ecm() changed in the SVN version.

Alex

Jeff Gilchrist · 2009-04-28, 00:05

Ok the msieve 1.41 Windows binaries have been updated and should fix the ecm messages:
http://gilchrist.ca/jeff/factoring/

Jeff.

Jeff Gilchrist · 2009-04-29, 23:43

I just experienced something strange with msieve 1.41 64bit Linux binary trying to generate a polynomial for a C93.

Code:

Wed Apr 29 17:21:26 2009  Msieve v. 1.41
Wed Apr 29 17:21:26 2009  random seeds: c122cfc2 84ad251c
Wed Apr 29 17:21:26 2009  factoring 258382100463852506230968335487805430257100969220134618900431126539928243525631289673555119871 (93 digits)
Wed Apr 29 17:21:27 2009  no P-1/P+1/ECM available, skipping
Wed Apr 29 17:21:27 2009  commencing number field sieve (93-digit input)
Wed Apr 29 17:21:27 2009  commencing number field sieve polynomial selection
Wed Apr 29 17:21:27 2009  time limit set to 0.17 hours
Wed Apr 29 17:21:27 2009  searching leading coefficients from 1 to 1391

So it says the search time is 0.17 hours, but I came back about 2 hours later to find it still running. The msieve.dat.p file had grown to 7.4MB and it was still outputting "save ..." lines.

I can keep the output files you think they might be useful. I will start again to see if it is repeatable.

Jeff.

Jeff Gilchrist · 2009-04-30, 01:08

Re-running it again is doing the same thing, running it on my Windows binary I had to manually abort it after 37 minutes:

Quote:

Wed Apr 29 20:29:07 2009
Wed Apr 29 20:29:07 2009
Wed Apr 29 20:29:07 2009 Msieve v. 1.41
Wed Apr 29 20:29:07 2009 random seeds: 15293e90 40fcf5ce
Wed Apr 29 20:29:07 2009 factoring 258382100463852506230968335487805430257100969220134618900431126539928243525631289673555119871 (93 digits)
Wed Apr 29 20:29:07 2009 searching for 15-digit factors
Wed Apr 29 20:29:07 2009 commencing number field sieve (93-digit input)
Wed Apr 29 20:29:07 2009 commencing number field sieve polynomial selection
Wed Apr 29 20:29:07 2009 time limit set to 0.17 hours
Wed Apr 29 20:29:07 2009 searching leading coefficients from 1 to 1391
Wed Apr 29 21:06:25 2009 polynomial selection complete
Wed Apr 29 21:06:25 2009 R0: -883031736949739087
Wed Apr 29 21:06:25 2009 R1: 57082879721
Wed Apr 29 21:06:25 2009 A0: 6266881314943365656914920
Wed Apr 29 21:06:25 2009 A1: 897893990862562265988
Wed Apr 29 21:06:25 2009 A2: -1288386176110342
Wed Apr 29 21:06:25 2009 A3: -2615388070133
Wed Apr 29 21:06:25 2009 A4: 19679132
Wed Apr 29 21:06:25 2009 A5: 480
Wed Apr 29 21:06:25 2009 skew 31480.06, size 9.024937e-009, alpha -6.808240, combined = 7.871111e-009
Wed Apr 29 21:06:25 2009 elapsed time 00:37:18

hhh · 2009-04-30, 02:02

Going some Aliquot numbers, with Msieve 1.41 I got the error mentioned in post 63. (I am not sure anymore about the "Too many merge attempts"-error, I can't find it in the logs). I uploaded everything to Schickel, who ran the postprocessing with version 1.39, and everything just came out fine.

Code:

linear algebra completed 222519 of 223174 dimensions (99.7%, ETA 0h 0m)
lanczos halted after 3528 iterations (dim = 222925)
recovered 32 nontrivial dependencies

commencing square root phase
reading relations for dependency 1
read 111749 cycles
cycles contain 455893 unique relations
read 455893 relations
multiplying 366356 relations
multiply complete, coefficients have about 14.51 million bits
initial square root is modulo 215881931
prp52 factor: 7570380941541769441561745312556684037938683763298177
prp52 factor: 8145994460731835857997597172380480561830720426463929
elapsed time 00:29:25

I suspect it to be related with the fact that the factors have nearly the same size (same thing with post 63).

Of course I don't know if this a real regression from version 1.39 to 41, or if it's accidentally and one can't do anything about it. Just wanted to let you know. H.

Andi47 · 2009-04-30, 05:05

Quote:

Originally Posted by Jeff Gilchrist

I just experienced something strange with msieve 1.41 64bit Linux binary trying to generate a polynomial for a C93.

Code:

Wed Apr 29 17:21:26 2009  Msieve v. 1.41
Wed Apr 29 17:21:26 2009  random seeds: c122cfc2 84ad251c
Wed Apr 29 17:21:26 2009  factoring 258382100463852506230968335487805430257100969220134618900431126539928243525631289673555119871 (93 digits)
Wed Apr 29 17:21:27 2009  no P-1/P+1/ECM available, skipping
Wed Apr 29 17:21:27 2009  commencing number field sieve (93-digit input)
Wed Apr 29 17:21:27 2009  commencing number field sieve polynomial selection
Wed Apr 29 17:21:27 2009  time limit set to 0.17 hours
Wed Apr 29 17:21:27 2009  searching leading coefficients from 1 to 1391

So it says the search time is 0.17 hours, but I came back about 2 hours later to find it still running. The msieve.dat.p file had grown to 7.4MB and it was still outputting "save ..." lines.

I can keep the output files you think they might be useful. I will start again to see if it is repeatable.

Jeff.

To my experience, this is repeatable with ANY composite below ~c95. To my guess, the problem is that for small composites, the limit for "what is a good polynomial that needs to be saved" is too low, so msieve saves virtually *every* polynomial (and not just the best ones) - and saving boatloads of polynomials seemingly takes much more time than finding them.

I guess that msieve looks, how many time has passed, after each block done, so when it takes 4+ hours (my experience) to save zillions of polynomials for one block, it will never take a look at the clock and find out, that 15 minutes have passed.

IMHO it should be possible to solve this problem by just rising the limit for good polynomials to save for composites up to 94 or 95 digits.

fivemack · 2009-04-30, 09:32

I don't know if this is a variant on the problem that other users are having for small N, but I'm running (after tweaking the source code to let me use -nz 25.0,23.3,-15.5 to set the base-10 logs of the three bounds for a polynomial search on the command line) polynomial search on a 162-digit composite in 10k slices for a5=1..100000. The 1k-10k and 10k-20k have now both taken 100 hours CPU (to compare, 20k-30k took 64, 1-1k took 3, 40k-50k took 33) and I'm slightly concerned that they may be looping endlessly.

gdb tells me that they're at least calling and returning from root_sieve, so maybe all I need is patience, but for these large jobs it would be very nice to have a little more feedback as to what msieve is doing; I am of course capturing stderr and stdout, but it's been three days since the last line was added to either.

2009-04-27, 16:32	#81
jasonp Tribal Bullet Oct 2004 2⁴·13·17 Posts	The function prototypes for the top-level calls to P+-1 and ECM in GMP-ECM have had an extra argument added after v6.2.2 was released, and unfortunately msieve uses these calls and not the supported GMP-ECM interface (next release will definitely change that). Not sure if that's the problem here. I can see it being the issue if you use an old ecm.h but a new precompiled GMP-ECM lib... Last fiddled with by jasonp on 2009-04-27 at 16:34

2009-04-30, 02:02	#86
hhh Jun 2005 373 Posts	Going some Aliquot numbers, with Msieve 1.41 I got the error mentioned in post 63. (I am not sure anymore about the "Too many merge attempts"-error, I can't find it in the logs). I uploaded everything to Schickel, who ran the postprocessing with version 1.39, and everything just came out fine. Code: linear algebra completed 222519 of 223174 dimensions (99.7%, ETA 0h 0m) lanczos halted after 3528 iterations (dim = 222925) recovered 32 nontrivial dependencies commencing square root phase reading relations for dependency 1 read 111749 cycles cycles contain 455893 unique relations read 455893 relations multiplying 366356 relations multiply complete, coefficients have about 14.51 million bits initial square root is modulo 215881931 prp52 factor: 7570380941541769441561745312556684037938683763298177 prp52 factor: 8145994460731835857997597172380480561830720426463929 elapsed time 00:29:25 I suspect it to be related with the fact that the factors have nearly the same size (same thing with post 63). Of course I don't know if this a real regression from version 1.39 to 41, or if it's accidentally and one can't do anything about it. Just wanted to let you know. H.

2009-04-30, 09:32	#88
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 13×491 Posts	Timing problem for very small a5 and large N I don't know if this is a variant on the problem that other users are having for small N, but I'm running (after tweaking the source code to let me use -nz 25.0,23.3,-15.5 to set the base-10 logs of the three bounds for a polynomial search on the command line) polynomial search on a 162-digit composite in 10k slices for a5=1..100000. The 1k-10k and 10k-20k have now both taken 100 hours CPU (to compare, 20k-30k took 64, 1-1k took 3, 40k-50k took 33) and I'm slightly concerned that they may be looping endlessly. gdb tells me that they're at least calling and returning from root_sieve, so maybe all I need is patience, but for these large jobs it would be very nice to have a little more feedback as to what msieve is doing; I am of course capturing stderr and stdout, but it's been three days since the last line was added to either. Last fiddled with by fivemack on 2009-04-30 at 09:33

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-04-27, 16:16	#80
Jeff Gilchrist Jun 2003 Ottawa, Canada 2²·293 Posts	Ok so I just re-compiled 1.41 with GMP-ECM 6.2.3 and also MPIR 1.1.1 and now the message goes away. I can reproduce the messages as well on my machine but with the new build they are not there. Tonight when I get the chance I will update my website with new builds. So did something change in GMP-ECM 6.2.3 that might have fixed this? Didn't someone say that the interface to GMP-ECM changed slightly, could that be the issue? I might have been using SVN for the last build but this one is the tarball posted on the GMP-ECM site. Jeff.

2009-04-28, 00:05	#83
Jeff Gilchrist Jun 2003 Ottawa, Canada 494₁₆ Posts	Ok the msieve 1.41 Windows binaries have been updated and should fix the ecm messages: http://gilchrist.ca/jeff/factoring/ Jeff.