20090725, 01:12  #1 
Jul 2009
1F_{16} Posts 
Trial division software for Mersenne
I know one of the first prescreening steps for testing a potential Mersenne prime is trial division, reformulated as a simpler modpower 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. 
20090725, 01:49  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2·3·23·31 Posts 
Quote:
Factor=exponent_to_test,bits_factored_already,bits_to_factor_to e.g. to factor 2^507666011 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 nearinstant). Another factoring program is Factor5. It's much slower than Prime95, at least for one quick test I ran. Last fiddled with by MiniGeek on 20090725 at 01:50 

20090725, 02:59  #3  
"Kyle"
Feb 2005
Somewhere near M52..
3·5·61 Posts 
Quote:


20090725, 03:34  #4  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2×3×23×31 Posts 
Quote:
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 MiniGeek on 20090725 at 03:43 

20090725, 04:18  #5 
Jul 2009
31 Posts 
Thanks to both of you! These are exactly the kind of tools I was looking to learn about!
Last fiddled with by SPWorley on 20090725 at 04:18 
20090725, 04:35  #6  
"Kyle"
Feb 2005
Somewhere near M52..
3·5·61 Posts 
Quote:
Last fiddled with by Primeinator on 20090725 at 04:37 

20090725, 12:59  #7 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2×3×23×31 Posts 
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.

20090816, 00:23  #8  
Sep 2008
Kansas
7067_{8} Posts 
Quote:
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 1020K 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 50bit number is different than squaring a 70bit 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 32bit CUDA was only available. With rumors of a 64bit device handler for the Mac, I abandon the work. As of last week, the 64bit version has yet to surface. RichD. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sublinear complexity of trial division?  yih117  Math  5  20180202 02:49 
Mersenne trial division implementation  mathPuzzles  Math  8  20170421 07:21 
P95 trial division strategy  SPWorley  Math  8  20090824 23:26 
Mersenne trial division candidate counts  SPWorley  Math  5  20090822 14:36 
Need GMP trialdivision timings  ewmayer  Factoring  7  20081211 22:12 