mersenneforum.org Msieve 1.41 Feedback
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2009-04-27, 15:56   #78
mklasson

Feb 2004

25810 Posts

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. :)

Last fiddled with by mklasson on 2009-04-27 at 15:58

2009-04-27, 16:07   #79
Jeff Gilchrist

Jun 2003
Ottawa, Canada

117310 Posts

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.

 2009-04-27, 16:16 #80 Jeff Gilchrist     Jun 2003 Ottawa, Canada 100100101012 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-27, 16:32 #81 jasonp Tribal Bullet     Oct 2004 33×131 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-27, 17:29   #82
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

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

 2009-04-28, 00:05 #83 Jeff Gilchrist     Jun 2003 Ottawa, Canada 100100101012 Posts Ok the msieve 1.41 Windows binaries have been updated and should fix the ecm messages: http://gilchrist.ca/jeff/factoring/ Jeff.
 2009-04-29, 23:43 #84 Jeff Gilchrist     Jun 2003 Ottawa, Canada 3·17·23 Posts 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.
2009-04-30, 01:08   #85
Jeff Gilchrist

Jun 2003
Ottawa, Canada

3×17×23 Posts

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

 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, 05:05   #87
Andi47

Oct 2004
Austria

9B216 Posts
GNFS poly search for small composites

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.

 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

 Thread Tools

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

All times are UTC. The time now is 23:33.

Fri May 7 23:33:45 UTC 2021 up 29 days, 18:14, 0 users, load averages: 1.94, 1.78, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.