mersenneforum.org > Math Factors of Mersenne Numbers
 Register FAQ Search Today's Posts Mark Forums Read

2002-09-26, 16:22   #12
ewmayer
2ω=0

Sep 2002
República de California

5×2,351 Posts

Quote:
Originally Posted by asdf
I have found this, but I am not sure about it (especially because it contains an error

Quote:
 If p==1 mod 4 then k==3 or 0 mod 4. If p==3 mod 4 then k==0 or 1 mod 4 This gives us a nice try 2, skip 2 type pattern, so all that we have to do is set the initial value the factor, then add 2p or 4p according to the pattern.
Now, the 4p in that last part should be 6p. Is this statement correct? I am guessing in your statements that you say that p = 2qk+1, and this quote says that p is the exponent of the Mersenne.
Yes, it should be 2p and 6p, where here, whoever wrote this was using
p for the Mersenne exponent, rather than q (I believe this notation
is more common; I used q for the exponent to be consistent with the
notation used in the post i was replying to.) I encourage you to find
other such correlations (e.g exponent mod 3, 5, 7,...)

-Ernst

2004-07-17, 21:13   #13
ATH
Einyen

Dec 2003
Denmark

2·17·101 Posts

E.W.Mayer wrote:

Quote:
 Another thing that bears mentioning is that in fact there are additional rigorous correlations between the Mersenne exponent q modulo 3,4,5,... and k mod 3,4,5,... . Exploiting the simplest few of these can reduce the number of k's we need to try to achieve a desired factor-size bound by 75-80%.
Quote:
 Among other shortcuts, Prime95 trial factoring considers only the 16 congruence classes mod 120 (+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49) that might contain prime Mersenne factors. Thus it skips fourteen of the mod 120 congruence classes (+-9, +-15, +-25, +-33, +-39, +-55, and +-57) which satisfy +-1 mod 8 but are never prime.
Are there even more correlations for k and d=2kp+1 besides the 16 congruence classes mod 120? If yes where can I find them?

 2004-07-17, 21:16 #14 ATH Einyen     Dec 2003 Denmark 65528 Posts Are there any restrictions for factors of Mersenne numbers Mq where q is not prime for both even and odd q?
2004-07-19, 16:11   #15

"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts

Quote:
 Originally Posted by ATH Are there even more correlations for k and d=2kp+1 besides the 16 congruence classes mod 120? If yes where can I find them?
Well, you can further eliminate multiples of 7 by using congruence classes mod 840, and so on.

2004-07-20, 12:50   #16
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111110012 Posts

Quote:
 Originally Posted by cheesehead Well, you can further eliminate multiples of 7 by using congruence classes mod 840, and so on.
IIRC, sieving mod 840 does not help speeding up the algorithm...

Luigi

2004-07-24, 02:32   #17

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by ET_ IIRC, sieving mod 840 does not help speeding up the algorithm...
My answer addressed the mathematics, not algorithmic or programming concerns. Going to an 840 mod would indeed speed up the algorithm, but when one looks at programming considerations, one may decide that the (small) speed gain is not enough to be worth the side effects.

Example: Originally, when Prime95 found a factor during trial factoring, it continued looking for a smaller factor during the uncompleted passes. (I.e., if it found a factor that was 7 mod 120, it continued looking in the 11 mod 120, 13 mod 120, ... and 119 mod 120 congruence classes.) One might decide that going to the more-numerous congruence classes mod 840 was not worth the side effect of having to trudge through the extra passes. It's not so much the teeny-tiny extra time involved as it is the psychological effect of users seeing it go through perhaps almost 100 more passes instead of only a dozen more. (I'm not saying this is a killer objection in particular. I'm saying this is an example of a side effect that deserved to be considered.) Also, once the mod 120 version had been tested and posted for use, changing to mod 840 or 9240 or whatever would require proportionally more testing and updating than they would have if originally used. Also, George W. considers the value to overall GIMPS throughput versus the required effort to make the change, in contrast to the value/effort ratios of a long list of other potential speedups.

Last fiddled with by cheesehead on 2004-07-24 at 02:41

 2004-07-24, 14:00 #18 biwema     Mar 2004 3×127 Posts Maybe there is a slight improvement, if you use 96 passes out of 840 or 960 passes out of 9240 instead of 16 out of 120. With that change you have 1/7 and 1/11 less candidates, but these are divisible by 7 and 11 and hence sieved in the first 2 loops anyway. The only thing you get, is a little bit more dense sieving table, that you can put more candidates into the same space. Mathematically, the sieving gets more efficient, the bigger the sieving table gets, because the sieving limit can be higher. In the computer implementation, it is not recommended to define the table so large that the whole does not fit into the L1 cache. (I am pretty sure that George Woltman takes care of that). One possibility to optimize the sieving process is to define the size of the array to a size which is the product of the next few primes. For 840, the array would be 11*13*17 or so. In that array, the composite candidates can already be marked and the array can be copied, that it can be directly be taken for the next steps. If the copying is faster than deleting the array sieving these three primes, it will improve the whole a bit (A sieve is least efficient at small primes, because the steps are small and more of them are needed.) If we want to find factors as soon as possible, it makes sense to check the numbers in increasing order. Instead of finishing all stages for one bits, every stage can be sieved for 64 -64.1 bit first then 64.1 - 64.2 bit and so on. If these steps are too small (that can happen if the number of stages is too high), the time penalty for switching the stages is too high and we gain nothing. Here, an optimum needs to be found.

 Similar Threads Thread Thread Starter Forum Replies Last Post UberNumberGeek Factoring 51 2017-02-13 20:30 siegert81 Math 23 2014-03-18 11:50 devarajkandadai Miscellaneous Math 15 2012-05-29 13:18 devarajkandadai Miscellaneous Math 6 2006-01-04 22:44 Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 11:59.

Thu Feb 2 11:59:03 UTC 2023 up 168 days, 9:27, 1 user, load averages: 0.75, 0.91, 0.97