Msieve 1.44 feedback

[xilman]

Originally Posted by ixfd64

Since msieve labels factors as "prp##" (where ## is the number of digits in the factor), I assume that it uses a probabilistic primality test. If that is the case, it would be nice if msieve used a deterministic test instead.

Deterministic primality tests generally take longer than probabilistic ones, but I don't think it would make a big difference, since the time requires to check the divisors for primality is miniscule compared to what it takes to factor the number.

If you want it, why don't you implement it?

Or don't you want it enough?


Paul

[R.D. Silverman]

Originally Posted by frmky

I have a feature request. Can msieve keep two checkpoint files? That is, rather than overwriting an existing chk file, move an existing chk to ch2, then create a new chk?

I ask because I just had about the worst possible msieve scenario happen. The LA for 2,899- has been running since Jan. 30. Another process was recently started on the computer. Today, while writing the checkpoint, which apparently uses slightly more memory than just running the LA, the computer ran out of memory so the Linux kernel decided to kill msieve. In the middle of writing the checkpoint. So it is now corrupt. With about 130 hours remaining until completion. And of course this is on the scratch partition so there's no backup. Time to start over.

Which suggests, of course, that checkpoint files should be periodically
backed up as a matter of course........

[jasonp]

Originally Posted by tmorrow

I was just worried that msieve might be in an infinite loop, it's the first time I've tried using my GPU for numerical computation purposes and was a little nervous about what was going on.

No harm in reporting what you see. Congrats on joining the number crunching elite :)

Originally Posted by CRGreathouse

Is there a way to see whether the polynomial selection is done on the CPU or GPU? I have an older (but still CUDA) graphics card and I'm curious to see if it's actually in use.

Does the extent of the polynomial selection depend on where it runs ([CG]PU) and on the relative speed of the GPU to the CPU? If I had a gazillion-Hz GPU (but a normal CPU), it would seem sensible to spend relatively more effort, if less time, on the polynomial selection compared to the rest. Or are improvements to the polynomial just negligible beyond a certain point?

GPUs are not used automatically; there is currently a CPU-only and a GPU-only version of msieve, although the two codebases are now pretty much merged together. The problem with building both into the same binary is that you would need Nvidia's libraries to link any binary at all, which is not fair to people who don't have nice graphics cards.

To answer you last question, nobody is sure of the maximum boost that a really excellent polynomial can supply, or at what point it becomes not worth the effort to keep searching. We have asymptotic formulas for the amount of work needed, but are not factoring infinitely large numbers :)

[ixfd64]

Originally Posted by xilman

If you want it, why don't you implement it?

I would, except I'm really bad at programming. :(

[xilman]

Originally Posted by ixfd64

I would, except I'm really bad at programming. :(

Ah, so you don't want it badly enough to learn how to become good at programming. Fair enough, as long as that's clear.

Paul

[FactorEyes]

I don't understand why so many are bothered by probabilistic primality tests.

As Knuth has pointed out, a Rabin-Miller test with 40 randomly-chosen bases is better than a single positive from a deterministic test. Your input number should have taken enough of an ECM beating to rule out factors as large as the square roots of most of your factors, anyway. The number of coincidences required for a composite factor to sneak through a sensible factorization is mind-boggling. ECM, p+1, or p-1 alone can pull composites, but one or more of these followed by a sieving run combined with a multi-base Rabin-Miller test at the end won't pull a composite factor in a million lifetimes.

Meanwhile, a deterministic test alone will give a false result due to hardware or software error far more often than that.

It doesn't hurt to run a deterministic test: I usually do, even though I feel silly wasting keystrokes.

We humans like certainty, I suppose. Mathematically-oriented humans, especially.

[xilman]

The 233 revision of msieve, which announces itself as v. 1.45, still has the crash in the sqrt phase which I reported for V. 1.44.

Building the CUDA version of the polynomial finder on a x86_64 RHEL5 system failed with numerous compiler errors. A non-CUDA build succeeded.

I've reported these problems to Jason and have sent him some gdb output which I hope will help him find the sqrt bug(s). I'll try to track down the CUDA problem(s) before posting more information.


Paul

[tmorrow]

I'm using msieve 1.44. After 2 days I had to interrupt a factorisation near the end of the polynomial selection and I'm now left with a large file of polynomials *.dat.p but no factor base file. How can I generate the factor base file without rerunning the entire polynomial selection again? I tried rerunning with the -d <min> option but it did not work.

[10metreh]

msieve.fb should look something like this:

N 519521494505946372166961846604854273057273321528705990560860399305888091695373809830325305678021403153
SKEW 20527.51
R0 -45378477119138364191
R1  20740976113
A0  972017581594890759167616
A1  778394302774536155236
A2  35712697796688196
A3 -2958425352503
A4 -133688922
A5  2700

c0-5 become A0-5, Y0 and Y1 become R0 and R1, skew and n are capitalised and all colons are removed.

[tmorrow]

Thanks 10metreh, that's partly helps. The *.fb files that get generated for me usually look like this:

N 6305604764586976841269783664936088420483838880263269680858295203306676242972755990421303899165854134868182618668693167359439172047257287
SKEW 1379657.59
A5 8820
A4 -7501580412
A3 -3844690699407269
A2 14058914127294867489133
A1 -10758406262487063406410421939
A0 -15763645027809005702506419350231605
R1 946820976388829
R0 -234883186419221822334578424
FAMAX 9800000
FRMAX 9800000
SALPMAX 268435456
SRLPMAX 268435456

So there's 4 parameters at the end I don't know how to generate. Furthermore, which polynomial from the 7871 in the *.dat.p file do I use? The one with the largest or smallest norm?

[debrouxl]

For those 4 parameters, I always let factMsieve.pl do the job for me (I guess factmsieve.py does that task as well).
I haven't looked at how FAMAX/FRMAX are calculated, but I know that SALPMAX/SRLPMAX are 2^<number of bits for large primes>.