memory usage in stage 2 of P-1 factoring

[gckw]

I was reading the readme.txt and it said the stage 2 of P-1 factoring would be more efficient if there's more memory allocated for use. How does it actually use the memory more efficiently, such as using 512mb instead of 8mb of memory. Does the factoring run faster? Also, it stated
"If at all in doubt, leave the settings at 8MB. The worst that will
happen is you end up running a Lucas-Lehmer primality test when stage 2
of P-1 factoring would have found a factor."

Does it mean that using less memory would yield of a higher probability of NOT finding a factor?

[ET_]

Does it mean that using less memory would yield of a higher probability of NOT finding a factor?

Sort of.

Stage 2 of P-1 factoring allocates memory to "make comparisons" and try to find a factor. The more memory you devote to stage 2, the more the chance to find a factor grows. But AFAIK we're talking of 1-2% of probability.

Luigi

[ewmayer]

Originally Posted by ET_

Sort of.

Stage 2 of P-1 factoring allocates memory to "make comparisons" and try to find a factor. The more memory you devote to stage 2, the more the chance to find a factor grows. But AFAIK we're talking of 1-2% of probability.

Luigi

No, what is happening is that stage 2 precomputes a set of even powers of the stage 1 residue R, e.g. R^2, R^4, etc. If your stage 2 primes limit is B2 and the largest gap between primes < B2 is no more than your largest precomputed power, then you need only do one modular multiply by one of your precomputed powers to cover the gap between consecutive primes. If you have less memory, you'll need to occasionally do an extra mul by two of precomputed powers of R to cover a large gap between primes, which costs extra CPU time. But the percentage of such extra muls decreases rapidly with extra allocated memory, so at some point (perhaps a few dozen precomputed powers, say enough to go up to R^50) you get rapidly diminishing returns. R^50 would imply 25 precomputed even powers of the stage 1 residue R, so for a 1024K-length FFT that would be 8MB per power, i.e. around 200MB. In other words, the difference between 256MB and 512MB allocated memory is likely to be slight.

[patrik]

And the reason the probablity of finding a factor increases is that the program choses higher bounds B1 and B2 to factor to when it is allocated more memory and can run more effectively.