Trial division software for Mersenne

[SPWorley]

I know one of the first pre-screening steps for testing a potential Mersenne prime is trial division, reformulated as a simpler mod-power evaluation, and tested with a set of trial divisors with certain properties.

This is all summarized quite well here.


Is there software for doing this step manually? What tool(s) exist for running such trial divisions on a candidate? Prime95 itself must have this built into itself for the GIMP project but it's not a seperate mode or user option (is it?)

My interest is more about designing parallelization algorithms, and this sounds like a promising task to analyze. Even though others have done it before and tuned it, it's a good learning experience to see how I can do, and have some reference compare speed and correctness to.

[Mini-Geek]

Originally Posted by SPWorley

Prime95 itself must have this built into itself for the GIMP project but it's not a seperate mode or user option (is it?)

It does, (have it built in) and it is (available as a separate option). Use
Factor=exponent_to_test,bits_factored_already,bits_to_factor_to
e.g. to factor 2^50766601-1 from 68 to 69 bits, use:
Factor=50766601,68,69
Note that k=1 for M50766601 has 27 bits, so for large numbers low bit sizes will have no possible factors (I don't think Prime95 even lets you check for factors with an upper limit of below 40 bits, which is near-instant).
Another factoring program is Factor5. It's much slower than Prime95, at least for one quick test I ran.

[Primeinator]

Originally Posted by Mini-Geek

It does, (have it built in) and it is (available as a separate option). Use
Factor=exponent_to_test,bits_factored_already,bits_to_factor_to
e.g. to factor 2^50766601-1 from 68 to 69 bits, use:
Factor=50766601,68,69
Note that k=1 for M50766601 has 27 bits, so for large numbers low bit sizes will have no possible factors (I don't think Prime95 even lets you check for factors with an upper limit of below 40 bits, which is near-instant).
Another factoring program is Factor5. It's much slower than Prime95, at least for one quick test I ran.

I believe (but don't quote me as I'm not 100% sure) that Factor5 is optimized for billion digit candidates and not "small" exponents <50M

[Mini-Geek]

Originally Posted by Primeinator

I believe (but don't quote me as I'm not 100% sure) that Factor5 is optimized for billion digit candidates and not "small" exponents <50M

Well, considering Prime95 doesn't work with billion digit candidates, I'd say it's about ∞% faster than Prime95 for billion digit candidates. (but only if 1=2...or is it?) Billion digit-ers start at p=~3.3B. Prime95 has a limit of p=2B (=2,000,000,000=2*10^9) Uncoincidentally, unless I'm doing something wrong, a signed 32-bit integer's limit is about 2.1B, and Prime95 has errors like it's looping around (saying it's rejecting some negative number) when you get about above that. For as far as it can go, though, Prime95 is faster by far. It could probably go quite a bit further if it wasn't for how Prime95 reads in (and possibly internally handles) exponents.
Here's another factoring tool: Mfactor. I'm not going to test out its speed right now, but it can factor any p < 2^50 (just over 1 quadrillion, making about 3.4*10^14, or almost 339 trillion, decimal digits!)

[SPWorley]

Thanks to both of you! These are exactly the kind of tools I was looking to learn about!

[Primeinator]

Originally Posted by Mini-Geek

Well, considering Prime95 doesn't work with billion digit candidates, I'd say it's about ∞% faster than Prime95 for billion digit candidates. (but only if 1=2...or is it?) Billion digit-ers start at p=~3.3B. Prime95 has a limit of p=2B (=2,000,000,000=2*10^9) Uncoincidentally, unless I'm doing something wrong, a signed 32-bit integer's limit is about 2.1B, and Prime95 has errors like it's looping around (saying it's rejecting some negative number) when you get about above that. For as far as it can go, though, Prime95 is faster by far. It could probably go quite a bit further if it wasn't for how Prime95 reads in (and possibly internally handles) exponents.
Here's another factoring tool: Mfactor. I'm not going to test out its speed right now, but it can factor any p < 2^50 (just over 1 quadrillion, making about 3.4*10^14, or almost 339 trillion, decimal digits!)

I see your point, but I think "∞%" is somewhat of an impossibility by definition. Can the 64 bit version of Prime95 factor above this limit?

[Mini-Geek]

Originally Posted by Primeinator

I see your point, but I think "∞%" is somewhat of an impossibility by definition. Can the 64 bit version of Prime95 factor above this limit?

Haha, hence the "but only if 1=2", since saying (speed of Factor5)/(speed of Prime95)=∞ equates division by zero with infinity, and as we all know, allowing division by zero makes all mathematical reason breaks down.

[RichD]

Originally Posted by SPWorley

My interest is more about designing parallelization algorithms, and this sounds like a promising task to analyze. Even though others have done it before and tuned it, it's a good learning experience to see how I can do, and have some reference compare speed and correctness to.

About a year ago I started a project (more proof of principle than a distributed project) along these same lines. I broke it down into three general processes.

1) The control routines on the host computer.

2) The squaring algorithm on the device.

3) The division or modulus algorithm on the device. (It is called residue is these forums.)

The idea was to continually feed a block of 10-20K candidates but reduce it down to a few hundred before spawning the device kernels and place each step into various queues.

It is a repetitive process to square (optionally double) and then divide. Even though division is a bit complex for large numbers, it is further simplified by only needing the residue.

Since the code path on the device works best if every worker follows the exact same set of instructions. Therefore, the squaring queues for the device is broken into various "sizes" and likewise with division/residue. i.e., the code path for squaring a 50-bit number is different than squaring a 70-bit number.

If I remember correctly the optimum use of the device is when the number of workers in a kernel is a multiple of 192 (3 * 64).

At the time a 32-bit CUDA was only available. With rumors of a 64-bit device handler for the Mac, I abandon the work. As of last week, the 64-bit version has yet to surface.

RichD.