mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-04-27, 15:56   #78
mklasson
 
Feb 2004

2·3·43 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
mklasson is offline   Reply With Quote
Old 2009-04-27, 16:07   #79
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7·167 Posts
Default

Quote:
Originally Posted by mklasson View Post
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 is offline   Reply With Quote
Old 2009-04-27, 16:16   #80
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

116910 Posts
Default

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.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-04-27, 16:32   #81
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2009-04-27, 17:29   #82
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
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
akruppa is offline   Reply With Quote
Old 2009-04-28, 00:05   #83
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

100100100012 Posts
Default

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

Jeff.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-04-29, 23:43   #84
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7×167 Posts
Default

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 is offline   Reply With Quote
Old 2009-04-30, 01:08   #85
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

100100100012 Posts
Default

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
Jeff Gilchrist is offline   Reply With Quote
Old 2009-04-30, 02:02   #86
hhh
 
hhh's Avatar
 
Jun 2005

373 Posts
Default

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.
hhh is offline   Reply With Quote
Old 2009-04-30, 05:05   #87
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default GNFS poly search for small composites

Quote:
Originally Posted by Jeff Gilchrist View Post
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.
Andi47 is offline   Reply With Quote
Old 2009-04-30, 09:32   #88
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23·3·5·53 Posts
Default 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
fivemack is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 02:47.

Mon Sep 28 02:47:08 UTC 2020 up 17 days, 23:58, 0 users, load averages: 1.35, 1.49, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.