mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2010-12-15, 15:17   #1
tichy
 
Nov 2010

22×19 Posts
Default 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 2010-12-15 at 15:18
tichy is offline   Reply With Quote
Old 2010-12-15, 15:37   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts
Default

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^p-1 (p prime) are of the form 2*k*p+1, where k is a positive integer. The only time that two Mersenne numbers, 2^p-1 and 2^q-1, (p and q prime) can share a factor is when k in 2*k*p+1 divides q or vice versa.
Mini-Geek is offline   Reply With Quote
Old 2010-12-15, 15:40   #3
tichy
 
Nov 2010

1148 Posts
Default

Ah, right, missed that. Thanks.
tichy is offline   Reply With Quote
Old 2010-12-16, 00:52   #4
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Quote:
Originally Posted by tichy View Post
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.
To be clearer the exponent of the Mersenne numbers differs over 6 bits in this example.

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.
only_human is offline   Reply With Quote
Old 2010-12-16, 11:43   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×52×47 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 7 Speedup Primeinator Software 13 2009-11-07 11:06
GGNFS SVN 374 with 11e siever: Speedup for c85-95! Andi47 Aliquot Sequences 0 2009-11-02 16:41
Holy Speedup, Batman! R.D. Silverman NFSNET Discussion 4 2008-10-02 01:28
More RAM = Speedup?? dave_0273 Hardware 8 2004-06-23 05:15
Mp factoring speedup question. Fusion_power Math 11 2004-06-03 08:25

All times are UTC. The time now is 17:37.

Wed Jul 15 17:37:25 UTC 2020 up 112 days, 15:10, 1 user, load averages: 2.22, 1.91, 1.79

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.