Math

[ET_]

Newbie question.

We all know the limitations that a Mersenne factor should accomplish:

- form of 2kp+1
- factor prime
- 1 or 7 mod 8
- 16 definite residual classes out of 120 (or 910 out of 4620)

Are there more/different clauses to follow for double Mersenne numbers?

Luigi

[axn]

Originally Posted by ET_

- form of 2kp+1
- factor prime
- 1 or 7 mod 8

Only these are the "true" limitations.

Originally Posted by ET_

- 16 definite residual classes out of 120 (or 910 out of 4620)

This is not a true limitation. This is just a consequence that the candidate factor be prime (i.e. no small factors).

Originally Posted by ET_

Are there more/different clauses to follow for double Mersenne numbers?

Not that I know of.

[LaurV]

We only know the first 3. There is no theoretical "jailbreak" since long-long time. The rest of the "rules", and all the modern tricks involved in programs like mfaktc, etc, are consequences of how we combine the first 3 rules, they don't bring anything new. The "classes" stuff are just special conditions we put for k depending on p (and BTW, your numbers are wrong).

For example, we say "if p=1 (mod 4), then".... (from the condition 1 and 3 you get that the factor is either 8xp+1 or 8xp+6p+1). Or "if p=3 (mod 4), then".... (from the condition 1 and 3 you get that the factor is either 8xp+1 or 8xp+2p+1). This is the same as renaming k into 4k and respective 4k+3, the factors 1 (mod 8) will be 8kp+1 and the others viceversa. Adding p=1 (mod 3) and so on (working it mod 5, 7, 11, with 2^2 or 2^3), you get the whole lot of "classes" (like 4 from 12, 32 from 120, 96 from 420, or 960 from 4620, etc), because if k is not in one of the remaining classes, then either condition 2 is not satisfied (q is not prime) or condition 3 is not (for where we used 2^3).

At the end everything is the first 3 rules and the chinese reminder theorem: if p is in THIS particular class (mod 4620), then k must be in THAT particular class (mod 4620) to get the right factor satisfying (1+2+3). And because p is prime, it can only be in "eulerphi(4620)" possibilities, which is 960. For each of them, the class of k is "computed".

Well, somehow.

[science_man_88]

Originally Posted by LaurV

We only know the first 3. There is no theoretical "jailbreak" since long-long time. The rest of the "rules", and all the modern tricks involved in programs like mfaktc, etc, are consequences of how we combine the first 3 rules, they don't bring anything new. The "classes" stuff are just special conditions we put for k depending on p (and BTW, your numbers are wrong).

For example, we say "if p=1 (mod 4), then".... (from the condition 1 and 3 you get that the factor is either 8xp+1 or 8xp+6p+1). Or "if p=3 (mod 4), then".... (from the condition 1 and 3 you get that the factor is either 8xp+1 or 8xp+2p+1). This is the same as renaming k into 4k and respective 4k+3, the factors 1 (mod 8) will be 8kp+1 and the others viceversa. Adding p=1 (mod 3) and so on (working it mod 5, 7, 11, with 2^2 or 2^3), you get the whole lot of "classes" (like 4 from 12, 32 from 120, 96 from 420, or 960 from 4620, etc), because if k is not in one of the remaining classes, then either condition 2 is not satisfied (q is not prime) or condition 3 is not (for where we used 2^3).

At the end everything is the first 3 rules and the chinese reminder theorem: if p is in THIS particular class (mod 4620), then k must be in THAT particular class (mod 4620) to get the right factor satisfying (1+2+3). And because p is prime, it can only be in "eulerphi(4620)" possibilities, which is 960. For each of them, the class of k is "computed".

Well, somehow.

for Double Mersenne Primes all P=3 mod 4 and all P=7 or 31 mod 120 is all the limits I can come up with. the mod 120 values might give information about k but that's about it.

[science_man_88]

to clear things up P=2^p-1 , second a thing I saw a while ago:

MM_x = MM_x-1*(2^2[SUP]x-1[/SUP]+2)+1

sorry just realized that the 2nd 2 is not supposed to be in the exponent