20170418, 02:03  #1 
Mar 2017
36_{8} Posts 
Mersenne trial division implementation
I was reading the great wiki on the stages of Mersenne testing. The initial filtering step is trial division. After some sieving and modular rejection, you still end up with various primes which are worthwhile to explicitly test as factors. And the wiki says "The remaining potential factors are tested using the [traditional generic] modular powering algorithm above." Is this correct? Is the best Mersenne hunting software literally using the classic powermod evaluation, or is are there any enhancements since you know you're taking the modulus of a number with the very simple form of \(2^n\)?
Put another way, Is there a especially good way to efficiently evaluate \(2^n \mod m\) as opposed to a generic \(a^n \mod m\)? I can imagine that you could speed up the squareandmultiply loop with an especially efficient Brauer \(2^k\)ary ladder since you can build any \(2^b\) for \(b < \log_2 m\) for free by simply left shifting a single bit by \(b\). That should save about 1/3 of the modular multiplies, but you still need to do the \(\log_2 n\) squarings. If \(n\) is large enough it would eventually be useful to use Montgomery multiplication instead, but you'd lose the elegant "shift a bit" ladder and again it'd be no different for \(2^n\) than a generic \(a^n\). Are there any other speedup tricks or is it really like the wiki says and it's still really just the classic squareandmultiply modular powering algorithm? 
20170418, 11:23  #2  
"Forget I exist"
Jul 2009
Dumbassville
8369_{10} Posts 
Quote:
http://primes.utm.edu/glossary/xpage...entiation.html also suggest they could go left to right binary exponentiation but that's a time versus space tradeoff. Last fiddled with by science_man_88 on 20170418 at 11:27 

20170418, 19:48  #3 
Mar 2017
2×3×5 Posts 
An extremely similar question comes up when doing the precompute necessary for Montgomery multiplication of any number, since you almost always use a computational base like \(R=2^{64i}\) for some convienient \(i\). The onetime precompute needs to find the modular inverse of R in the base in question, usually using the extended Euclidian algorithm. So, is there any special method or optimization to computing \((2^n)^{1}\mod m?\)
Last fiddled with by mathPuzzles on 20170418 at 19:49 
20170418, 19:53  #4  
Mar 2017
2×3×5 Posts 
Quote:


20170418, 21:36  #5  
∂^{2}ω=0
Sep 2002
República de California
3^{2}·1,093 Posts 
Quote:
Quote:


20170419, 00:47  #6 
Mar 2017
30_{10} Posts 
That's very interesting and exactly what I'm trying to learn! So what is this method to compute \((2^n)^{1}\mod m\) without eGCD? Perhaps some variant in the flavor of the binary GCD?

20170419, 02:57  #7  
∂^{2}ω=0
Sep 2002
República de California
3^{2}×1,093 Posts 
Quote:


20170421, 03:47  #8 
Mar 2017
2×3×5 Posts 
ewmayer, you're right, I swapped the R and modulus value in my question. But your answer is also part of what I'm trying to learn! Now I have to study your paper. It's looks like part of the solution to my efficiency puzzle. I appreciate it!

20170421, 07:21  #9 
∂^{2}ω=0
Sep 2002
República de California
3^{2}·1,093 Posts 
Algorithm E in the paper has an efficient modpow based on Montgomerymul, but I encourage you to try to slog though the preceding material, as well. :) I included several worked 64bitmodulus examples; hopefully you will find those useful.

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