Factors of Mersenne Numbers

[ewmayer]

Originally Posted by asdf

I have found this, but I am not sure about it (especially because it contains an error

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

[ATH]

E.W.Mayer wrote:

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%.

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?

[ATH]

Are there any restrictions for factors of Mersenne numbers Mq where q is not prime for both even and odd q?

[cheesehead]

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.

[ET_]

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

[cheesehead]

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.

[biwema]

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.