mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2012-09-20, 08:36   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25·149 Posts
Default Math

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
ET_ is offline   Reply With Quote
Old 2012-09-20, 09:23   #2
axn
 
axn's Avatar
 
Jun 2003

4,723 Posts
Default

Quote:
Originally Posted by ET_ View Post
- form of 2kp+1
- factor prime
- 1 or 7 mod 8
Only these are the "true" limitations.

Quote:
Originally Posted by ET_ View Post
- 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).

Quote:
Originally Posted by ET_ View Post
Are there more/different clauses to follow for double Mersenne numbers?
Not that I know of.
axn is offline   Reply With Quote
Old 2012-09-20, 09:39   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

212548 Posts
Default

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.

Last fiddled with by LaurV on 2012-09-20 at 09:42
LaurV is offline   Reply With Quote
Old 2012-09-20, 14:37   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 is offline   Reply With Quote
Old 2012-09-20, 19:33   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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

MMx = MMx-1*(22[SUP]x-1[/SUP]+2)+1

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

Last fiddled with by science_man_88 on 2012-09-20 at 19:40
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I am so sorry for being bad at math. Aramis Wyler Math 40 2014-12-18 11:15
need some math help. swl551 Math 2 2014-02-20 16:33
Math JohnFullspeed Forum Feedback 1 2011-07-11 16:42
math help pls! DSC Miscellaneous Math 2 2005-09-11 04:53
help with math DSC Homework Help 13 2005-08-31 07:16

All times are UTC. The time now is 10:22.

Sat Oct 31 10:22:18 UTC 2020 up 51 days, 7:33, 2 users, load averages: 1.64, 1.66, 1.92

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.