Msieve 1.44 feedback

[Jeff Gilchrist]

Originally Posted by jasonp

Yuck, I figured that was so rare that it wasn't worth worrying about. The changes are easy and I'll make them.

PS: split checkpoint writes now available in SVN

That happened to me once too but instead of running out of RAM the partition became full and ran out of disk space so I had a partially-save checkpoint file. Luckily I was manually backing up my .chk files every 10% so didn't lose too much.

Great to see the split option as an extra safety measure, especially for these 6+ week jobs.

Jeff.

[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.

[CRGreathouse]

(inadvertently left out from above post)
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?

[tmorrow]

I'm using msieve 1.44. I've tried the CUDA enabled version for the first time, on a C124. I'm using Brian Gladman's factmsieve.py python wrapper.

The msieve program is not performing as I would expect, it seems to be stuck in the polynomial selection, ignoring the imposed time limit for that step. Going off the log's I see

Msieve v. 1.44
Thu Mar 04 04:38:29 2010
random seeds: d72f8468 d350f57a
factoring 1029209400397104276975667257077734617786511861853948894747621655086416232629238887842405035196128848790659536566713324838677 (124 digits)
searching for 15-digit factors
commencing number field sieve (124-digit input)
commencing number field sieve polynomial selection
time limit set to 6.35 hours
searching leading coefficients from 1 to 47152
using GPU 0 (GeForce 9800 GX2)
deadline: 100 seconds per coefficient

However, after 7 hours the polynomial selection is still going on. The software is not adhering to its self imposed time limit of 6.35 hours? What is the best action for me to take at this point?

Stop Press: Ok I jumped the gun. After elapsed time 7:48.10 msieve completed the polynomial selection. I guess the time limit is an estimate of how long the task will take and not a hard limit of how long it will spend on the task. Perhaps "Time limit estimated at" would be more better than "Time limit set to".

[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.

[jasonp]

Does msieve.dat.p contain any polynomials? Adhering to a self-imposed time limit can be difficult sometimes, because stage 1 can be interrupted early but stage 2 will not get interrupted, and could take a long time with a very good hit in stage 1. Ah, I see it finished. If you have a hard limit you can run msieve with '-d <num>', which will cause an interrupt and graceful shutdown after <num> minutes. This interrupt typically happens very quickly.

Edit: pseudoprimality uses 20 iteration of Rabin-Miller with random bases. Adding primality proving is a matter of doing a bunch of development I don't much care for (or have the time for).

[mdettweiler]

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.

I realize this doesn't answer your question, but it may be useful anyway: if you submit your factors to www.factordb.com, they are automatically checked with a deterministic primality test (APR-CL to be specific, pardon me if I got the acronym wrong). Recently the database's work queue has been rather bogged down so it doesn't always get to prove factors right away, but it usually does them within a few minutes.

[Batalov]

...or throw them in http://www.alpertron.com.ar/ECM.HTM
and APRT-CL will be under your control, and under a minute.
(factorDB sometimes doesn't tend to PrP proofs for days)

[Mini-Geek]

...or use PARI/gp's isprime() command. (isprime() is deterministic, ispseudoprime() is probabilistic)

[tmorrow]

Originally Posted by jasonp

Does msieve.dat.p contain any polynomials? Adhering to a self-imposed time limit can be difficult sometimes, because stage 1 can be interrupted early but stage 2 will not get interrupted, and could take a long time with a very good hit in stage 1. Ah, I see it finished. If you have a hard limit you can run msieve with '-d <num>', which will cause an interrupt and graceful shutdown after <num> minutes. This interrupt typically happens very quickly.

Thanks for the help Jason. I have a 3MB file full of polynomials - many more than usual so that's a good thing. The selected best poly is now being used in the sieving on 3 cpu's, each at a rate of 0.01256 sec/rel (80 rel/sec) which seems quite satisfactory.

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.

[mdettweiler]

Originally Posted by Mini-Geek

...or use PARI/gp's isprime() command. (isprime() is deterministic, ispseudoprime() is probabilistic)

In fact, PARI's isprime() is actually what the FactorDB uses to do its APRT-CL proofs. (I think isprime() can also be used to perform other sorts of deterministic tests, though APRT-CL is the default.)