mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-07-25, 01:12   #1
SPWorley
 
Jul 2009

31 Posts
Default Trial division software for Mersenne

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.
SPWorley is offline   Reply With Quote
Old 2009-07-25, 01:49   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by SPWorley View Post
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.

Last fiddled with by Mini-Geek on 2009-07-25 at 01:50
Mini-Geek is offline   Reply With Quote
Old 2009-07-25, 02:59   #3
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

15768 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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
Primeinator is offline   Reply With Quote
Old 2009-07-25, 03:34   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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!)

Last fiddled with by Mini-Geek on 2009-07-25 at 03:43
Mini-Geek is offline   Reply With Quote
Old 2009-07-25, 04:18   #5
SPWorley
 
Jul 2009

111112 Posts
Default

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

Last fiddled with by SPWorley on 2009-07-25 at 04:18
SPWorley is offline   Reply With Quote
Old 2009-07-25, 04:35   #6
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

2·3·149 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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?

Last fiddled with by Primeinator on 2009-07-25 at 04:37
Primeinator is offline   Reply With Quote
Old 2009-07-25, 12:59   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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.
Mini-Geek is offline   Reply With Quote
Old 2009-08-16, 00:23   #8
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

318110 Posts
Default

Quote:
Originally Posted by SPWorley View Post
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.
RichD is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sublinear complexity of trial division? yih117 Math 5 2018-02-02 02:49
Mersenne trial division implementation mathPuzzles Math 8 2017-04-21 07:21
P95 trial division strategy SPWorley Math 8 2009-08-24 23:26
Mersenne trial division candidate counts SPWorley Math 5 2009-08-22 14:36
Need GMP trial-division timings ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 02:28.

Sat Dec 5 02:28:19 UTC 2020 up 1 day, 22:39, 0 users, load averages: 1.25, 1.37, 1.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.