20101215, 15:17  #1 
Nov 2010
2^{2}×19 Posts 
TF speedup suggestion
Hi,
I've got sort of an idea how to speed up Trial Factoring. Consider 7 consecutive Mersenne numbers in a range 80051776  80051837. This Mersenne numbers are: M(80051779) M(80051789) M(80051791) M(80051813) M(80051819) M(80051821) M(80051837) In binary representation they differ only at the 6 least significant bits. During Trial Factoring the exponents are evaluated from MSBs, so for the 21 MSBs for each of the above Mersenne numbers intermediate result of TF for a given factor will be the same. Only the last 6 bits will need separate path of calculation. Moreover, if we do modular squaring for the first differing bit, then from the case when it is 0 we obtain the result for the case of 1 for almost free. So in fact only the 5 LSBs will need separate calculation. Thus, my suggestion is to perform Trial Factoring for packets on Mersenne number candidates. The resulting speedup due to not repeating reduntant calculations will be substantial. In the naive estimation each of these Mersenne Numbers will need about 22 modular multiplications (I assume for the first five or so MSBs the result can be easily tabularized). With traditional approach for seven Mersenne Numbers this translates to 22*7=154 modular multiplications. With "parallel" processing of these seven MNs we will process first 22 MSBs in a single run and then branch for each MN to finish Trial Factoring with the remaining LSBs  this will require approximately 7*5 = 35 modular multiplications, a total of roughly 35+15 = 50, what is slightly more than a traditional cost for Trial Factoring of two MNs. Any thoughts on this sugegstion will be appreciated. Thanks, Last fiddled with by tichy on 20101215 at 15:18 
20101215, 15:37  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10253_{8} Posts 
I'm not sure if the idea even could work when you are checking multiple candidates for the same factor, but there's a bigger problem:
Different Mersenne numbers share few, if any, possible factors for you to check simultaneously. The reason is that factors of a number 2^p1 (p prime) are of the form 2*k*p+1, where k is a positive integer. The only time that two Mersenne numbers, 2^p1 and 2^q1, (p and q prime) can share a factor is when k in 2*k*p+1 divides q or vice versa. 
20101215, 15:40  #3 
Nov 2010
114_{8} Posts 
Ah, right, missed that. Thanks.

20101216, 00:52  #4  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Quote:
This seem to be a mashup of two different ideas: 1) a desire to try to find a way to break the ModPow function into two parts, a most significant portion that could be calculated once (if possible) for several Mersenne numbers and a least significant portion that is calculated individually for each Mersenne number. 2) a blurry idea to "finish Trial Factoring" while computing the least significant portion of the ModPow function. 

20101216, 11:43  #5 
Tribal Bullet
Oct 2004
3×5^{2}×47 Posts 
I think only_human has the right interpretation of what the OP is asking. Unfortunately modular arithmetic doesn't work that way; a mod operation is nastily nonlinear, and once a 'wraparound' happens there is almost nothing you can say about what the remainder would have been given a slightly different modulus. Especially with an exponentiation, where many wraparounds have to happen before you get a final answer.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Windows 7 Speedup  Primeinator  Software  13  20091107 11:06 
GGNFS SVN 374 with 11e siever: Speedup for c8595!  Andi47  Aliquot Sequences  0  20091102 16:41 
Holy Speedup, Batman!  R.D. Silverman  NFSNET Discussion  4  20081002 01:28 
More RAM = Speedup??  dave_0273  Hardware  8  20040623 05:15 
Mp factoring speedup question.  Fusion_power  Math  11  20040603 08:25 