Actually, on that note: what's considered a "normal" density for the sparse part of the matrix? What value would be considered low?

[COLOR=green]_______[/COLOR]
[COLOR=green]SB: To maintain flow, I will answer here, inline.[/COLOR]
[COLOR=green]Default target density is 70, that's for the cycles' generation part (-nc1).[/COLOR]
[COLOR=green]The resulting matrices are slightly less dense, maybe 66?[/COLOR]
[COLOR=green][/COLOR]
[COLOR=green]However, many people used higher target density, 90, 100, 110 and up. Then the matrix density would be maybe a few units less. That sort of order of magnitude. [/COLOR]
[COLOR=green][/COLOR]
[COLOR=green]Red flag will show up in some last lines of nc1 output: the density of 15-20-30 would mean that the filtering was led astray with far too many relations.[/COLOR]

We prefer the term "white magic". ;-)

Jason wrote before that the reasons for this behavior are opaque, and a research around this is on his to do list but not very high; the main reason being, that the remedy exists and is not hard. You are not alone; many people had been in that "far too many relations" territory. The range between "too few" and "far too many" relations is quite wide. It is not a terrible problem.

I was happy to see that this was [I]not[/I] your large project (the snfs-290). That one happily on track, is it?

[QUOTE=Batalov;326205]We prefer the term "white magic". ;-)

Jason wrote before that the reasons for this behavior are opaque, and a research around this is on his to do list but not very high; the main reason being, that the remedy exists and is not hard. You are not alone; many people had been in that "far too many relations" territory. The range between "too few" and "far too many" relations is quite wide. It is not a terrible problem.

I was happy to see that this was [I]not[/I] your large project (the snfs-290). That one happily on track, is it?[/QUOTE]

Looks to be on track. The matrix is:

[code]Fri Jan 25 11:07:24 2013 matrix starts at (0, 0)
Fri Jan 25 11:07:29 2013 matrix is 31289277 x 31289453 (12587.6 MB) with weight 3718418753 (118.84/col)
Fri Jan 25 11:07:29 2013 sparse part has weight 2955581343 (94.46/col)
Fri Jan 25 11:07:29 2013 saving the first 48 matrix rows for later
Fri Jan 25 11:07:35 2013 matrix includes 64 packed rows
Fri Jan 25 11:07:40 2013 matrix is 31289229 x 31289453 (12151.2 MB) with weight 3104613918 (99.22/col)
Fri Jan 25 11:07:40 2013 sparse part has weight 2872469612 (91.80/col)[/code]

Current progress:

[code]linear algebra completed 2353752 of 31289453 dimensions (7.5%, ETA 1054h 9m)[/code]

Looks great, and see those relevant density values - they look fine.

Smooth sailing!

Loop in square root phase.
 

Hello,

Msieve is looping in the square root phase for one number. Numbers this size usually take a minute or two per square root, this had been running for more than 15 minutes when I killed it. I retried twice,same effect even staring with relation 2.

I also tried rerunning the linear algebra, same symptoms.

Screen output from the retries is:
[code]chris@linux-5hwg:~/ggnfs/tests/factordb/d2_408_136_-1> "/home/chris/ggnfs/bin/msieve" -s d2_408_136_-1.dat -l ggnfs.log -i d2_408_136_-1.ini -v -nf d2_408_136_-1.fb -t 2 -nc3


Msieve v. 1.50 (SVN 5May2012)
Sun Feb 10 09:17:27 2013
random seeds: 8859e284 e5f52c88
factoring 4631586437596625245001764793222167709863121954610655475010879318591207306519588836102977777021840585068400452551 (112 digits)
searching for 15-digit factors
commencing number field sieve (112-digit input)
R0: -295147905179352825856
R1: 1
A0: -1
A1: 0
A2: 1
A3: 0
A4: 0
A5: 0
A6: 1
skew 1.00, size 3.482e-06, alpha 2.641, combined = 2.927e-09 rroots = 2

commencing square root phase
reading relations for dependency 1
read 55424 cycles
cycles contain 181170 unique relations
read 181170 relations
multiplying 181170 relations
multiply complete, coefficients have about 3.42 million bits
warning: no irreducible prime found, switching to small primes

received signal 2; shutting down


chris@linux-5hwg:~/ggnfs/tests/factordb/d2_408_136_-1> "/home/chris/ggnfs/bin/msieve" -s d2_408_136_-1.dat -l ggnfs.log -i d2_408_136_-1.ini -v -nf d2_408_136_-1.fb -t 2 -nc3 2,34


Msieve v. 1.50 (SVN 5May2012)
Sun Feb 10 09:24:20 2013
random seeds: f896aecb 11046125
factoring 4631586437596625245001764793222167709863121954610655475010879318591207306519588836102977777021840585068400452551 (112 digits)
searching for 15-digit factors
commencing number field sieve (112-digit input)
R0: -295147905179352825856
R1: 1
A0: -1
A1: 0
A2: 1
A3: 0
A4: 0
A5: 0
A6: 1
skew 1.00, size 3.482e-06, alpha 2.641, combined = 2.927e-09 rroots = 2

commencing square root phase
reading relations for dependency 2
read 55325 cycles
cycles contain 180954 unique relations
read 180954 relations
multiplying 180954 relations
multiply complete, coefficients have about 3.42 million bits
warning: no irreducible prime found, switching to small primes

received signal 2; shutting down
[/code]And I've attached the log to the post.

I've got a backup of all the files in the directory if you want them.

Chris

PS. I'm not set up with SVN. The (SVN 5May2012) is because I put the date I downloaded msieve into the makefile.

Maybe x[SUP]6[/SUP]+x[SUP]2[/SUP]-1 is reducible modulo every prime?
Maybe there's a L/M factorization, given that x is an certain even power of 2?

Hi everyone,

I'm using msieve as a library for factoring integers in my master thesis regarding heavy numbercrunching and I'm very pleased :) It's doing its job wonderful so far, but every now and then I'm getting

"error: tiny factoring failed"

printing to stdout.

I looked around in "driver.c" of the source code and I was wondering: If this is an "error", meaning that the factorization has failed at some point, how can I as a API-user detect that?

As far as I can tell, this error is going to be thrown from[I] msieve_run_core()[/I] by returning 0 to [I]msieve_run()[/I]. But [I]msieve_run() [/I]doesn't seem to care and sets the MSIEVE_FLAG_FACTORIZATION_DONE flag to the msieve_obj. Does this just mean the algorithm has done its job by best effort to find as many factors as possible?

It sounds like you are using the quadratic sieve; the 'tiny factoring failed' errors are there because all of the small-input factorization subroutines only succeed with high probability, but the overall effort is not spoiled if that happens. It just means that you don't get to use one relation out of millions.

Also, if you are using QS I'd recommend switching to the implementation in YAFU (see the YAFU subforum and feel free to ask the very active developer community there for help). The Msieve QS code really has not been updated in the last ~5 years.

The handling of major errors that require an abort is not currently very graceful; the factorization driver in demo.c will just print out all the factors found, and most of the time a fatal error causes an error message and an abort from within the library. If the error actually causes a graceful exit, then the driver will print all factors currently found along with one composite (presumably what you were running the QS code on).

Thanks for the quick reply :smile: Yes, I'm using the quadratic sieve.

I'm going to try out YAFU. Too bad, your library was very easy to combine with my project. I will still recommend it to others.

I did a quick shot on yafu, but that doesn't work for me either :( So I added a bit of error handling in msieve to suit my needs. I've put an extra result-code field in msieve_obj and changed some of the (silent) errors to use it. I might do this with some more error-handling code in msieve, if you're interested, I'm willing to share.

We're always interested in changes, whether or not the original author appreciates them (but I'd be surprised if this one didn't, assuming your code is reasonable). I certainly would like to see it. :smile:

There has been much chatter and little work ("real life" and whatnot) about merging yafu and msieve -- they are very complementary and in order for either to be truly effective, the other is a necessity. You would be one of many who would benefit from such a merger (but again, it's not a very rewarding task to simply merge two existing projects).