mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > science_man_88

Closed Thread
 
Thread Tools
Old 2010-11-03, 15:38   #1
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default theory on Mersenne primes ?

Quote:
Originally Posted by science_man_88
I know that according to resource on the divisors of Mersenne numbers of prime index that aren't prime are +1/-1 mod 8 and of the form 2kp+1 which limits possible k values depending on the exponent mod 8 . I've look at all divisors of the exceptions to 2^37-1 so far it seems if p mod 6 =5 or 1 then 2 of the factors of 2^p-1 seem to be also the same modulo 6 is this verifiable if so could this be used to further reduce the k values needed to be checked ?
this is from a pm I sent (bet if ever pm I sent was deleted from people's inbox's the server would run faster lol)
science_man_88 is offline  
Old 2010-11-03, 16:12   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default

Note that all primes above 3 are either 1 or 5 mod 6.
Quote:
Originally Posted by science_man_88
I know that according to resource on the divisors of Mersenne numbers of prime index that aren't prime are +1/-1 mod 8 and of the form 2kp+1 which limits possible k values depending on the exponent mod 8 . I've look at all divisors of the exceptions to 2^37-1 so far it seems if p mod 6 =5 or 1 then 2 of the factors of 2^p-1 seem to be also the same modulo 6 is this verifiable if so could this be used to further reduce the k values needed to be checked ?
Another way to write 5 mod 6 is -1 mod 6. When p is odd, 2^p-1 is 1 mod 6.
If N is 1 mod 6, then there must be an even number of factors that are -1 mod 6 (because the factors mod 6 have to multiply to the number mod 6). As far as I can tell, this can't be used to make it easier to find factors.
Mini-Geek is offline  
Old 2010-11-03, 16:30   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Note that all primes above 3 are either 1 or 5 mod 6.

Another way to write 5 mod 6 is -1 mod 6. When p is odd, 2^p-1 is 1 mod 6.
If N is 1 mod 6, then there must be an even number of factors that are -1 mod 6 (because the factors mod 6 have to multiply to the number mod 6). As far as I can tell, this can't be used to make it easier to find factors.
well for the 1/-1 mod 8 as well if p=3 mod 8 as I've listed before k = 1,5,9,etc. for 7(-1) mod 8 and k=0,4,8,12,16 etc. for 1 mod 8, if p=5 mod 6 to get 1 mod 6 use k=0,3,6,9,etc. ? and for 5 mod 6 k= 1,4,7,etc. ? is so when do k match up for the given mod 8 and mod 6 such that they can equal a common thing number that can be a factor.
science_man_88 is offline  
Old 2010-11-03, 16:43   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
well for the 1/-1 mod 8 as well if p=3 mod 8 as I've listed before k = 1,5,9,etc. for 7(-1) mod 8 and k=0,4,8,12,16 etc. for 1 mod 8, if p=5 mod 6 to get 1 mod 6 use k=0,3,6,9,etc. ? and for 5 mod 6 k= 1,4,7,etc. ? is so when do k match up for the given mod 8 and mod 6 such that they can equal a common thing number that can be a factor.
Since only primes need to be considered for potential factors, all factors that are not 1 or 5 mod 6 are ignored anyway (all primes over 3 are 1 or 5 mod 6 because all other values mod 6 have 2 and/or 3 as factors). Factors that are 1 mod 6 still have to be tested, as do factors that are 5 mod 6. In the event that it'd be better to test 1 mod 6 and 5 mod 6 factors separately, it might be useful to find out which k's produce which sort of factor and work with that. IIRC, Prime95 does factors within a bit level according to their value mod 120 for efficiency, in which case the value mod 6 isn't at all helpful except in simple implementations.
I don't see any way this can be an improvement on current methods.

Last fiddled with by Mini-Geek on 2010-11-03 at 16:46
Mini-Geek is offline  
Old 2010-11-03, 17:10   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

31·191 Posts
Default

My understanding of sm88's idea: if you're factoring a number that is 5 mod 6, at least one of its prime divisors must be 5 mod 6. Can this be used to speed trial division? (This was stated only in the case of Mersenne numbers, but it seems to be more general.)

Generally, the answer seems to be "no". You could search only for primes that are 5 mod 6, but it's quite possible that all such primes are large -- greater than sqrt(n). In essence, you're trading a factor of 2 for a factor of sqrt(n) which is a losing proposition.

Example: Suppose you're factoring 15419076477348026044248723582269. There are about 1.12e14 primes below the square root of this number, so trial division will take at most this many divisions to factor the number. (In fact it will take 1.3926475881e10 divisions, since the smaller factor is 355894230031.)

But the smallest factor that is 5 mod 6 is 43324884688366413299. Now only about half the primes up to that number need be tested, but this is 4.9e17 which is not only greater than 1.4e10 but greater than 1.1e14.
CRGreathouse is offline  
Old 2010-11-03, 17:17   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

want an example of what I mean ? too bad I'll give you one anyways lol.

for p=11 p=3 mod 8

for factors 7 mod 8

k=1,5,9,etc. (4n+1)

for 1 mod 8

k=0,4,8,12

since they can be 6n+1 or 6n-1

since 11= 5 mod 6

6n+1 k=0,3,6,9, (3x+0)
6n-1 k = 1,4,7 (3x+1)

if we say we need at least 1 factor of the same type mod 6 then we only have to check when 4n+1 or 4n match up with 3x+1 and we should find possible factors k= 1,13,etc. because 4n+1 meets 3x+1 every fourth value and every 3rd value greater than index =2 for 4n this limits it to at most if we can figure on thing out i could narrow it down to finding factors on one or the other k list for mod 8 but anyways.
science_man_88 is offline  
Old 2010-11-03, 17:25   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
if we say we need at least 1 factor of the same type mod 6 then we only have to check when 4n+1 or 4n match up with 3x+1 and we should find possible factors k= 1,13,etc. because 4n+1 meets 3x+1 every fourth value and every 3rd value greater than index =2 for 4n this limits it to at most if we can figure on thing out i could narrow it down to finding factors on one or the other k list for mod 8 but anyways.
We don't always need at least 1 factor of the same type mod 6, and on large numbers we have no clue how many other factors there are. Consider a number that is 1 mod 6. It must have an even number of factors that are -1 mod 6, but that includes 0, 2, 4, etc. And it can have any number of factors that are 1 mod 6. It really doesn't help. It could have two factors that are -1 mod 6 and none that are 1 mod 6. Or 0 factors that are -1 mod 6 and 1 that is 1 mod 6 (a.k.a. it's prime), or anything else.
Yes, excluding k's that make 2kp+1 not 1 or 5 mod 6 narrows down the list. It removes a great deal of candidates, but it does so by removing all composites with 2 or 3 as a factor. You can find the same thing by just checking each 2kp+1 to see if it has 3 as a factor (since the form is 2kp+1, they're all odd, 2 can never be a factor). The question, then, is: Is it better to figure out which k's don't have some small numbers as factors and only consider those, or to first consider all k's and then remove them if they have the small factors? I'm pretty sure Prime95 and other modern implementations would have already asked this and have chosen the most efficient way.

Last fiddled with by Mini-Geek on 2010-11-03 at 17:34
Mini-Geek is offline  
Old 2010-11-03, 17:39   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

31×191 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Yes, excluding k's that make 2kp+1 not 1 or 5 mod 6 narrows down the list. It removes a great deal of candidates, but it does so by removing all composites with 2 or 3 as a factor. You can find the same thing by just checking each 2kp+1 to see if it has 3 as a factor (since the form is 2kp+1, they're all odd, 2 can never be a factor). The question, then, is: Is it better to figure out which k's don't have some small numbers as factors and only consider those, or to first consider all k's and then remove them if they have the small factors? I'm pretty sure Prime95 and other modern implementations would have already asked this and have chosen the most efficient way.
In other words: the idea works and is probably already in use, unless a yet better way has been found by the Prime95 crew.
CRGreathouse is offline  
Old 2010-11-04, 16:37   #9
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·977 Posts
Default

You want to combine those factors (2kp+1) = +/- 1 (mod 8) with those that can be prime (2kp+1)= +/- 1 (mod 6).

Prime95 already does this, but instead of using +/- 1 mod 6, it uses those numbers mod 120 which can be prime, i.e. those that are co-prime with 120:
1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113,119

Combining the above list with the requirement +/- 1 mod 8 gives 16 residue classes mod 120, which is those 16 Prime95 uses:
1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119

Your idea gives 20 residue classes mod 120:
1,7,17,23,25,31,41,47,49,55,65,71,73,79,89,95,97,103,113,119
so what Prime95 already uses is more efficient.
ATH is offline  
Old 2010-11-04, 17:03   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by ATH View Post
You want to combine those factors (2kp+1) = +/- 1 (mod 8) with those that can be prime (2kp+1)= +/- 1 (mod 6).

Prime95 already does this, but instead of using +/- 1 mod 6, it uses those numbers mod 120 which can be prime, i.e. those that are co-prime with 120:
1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113,119

Combining the above list with the requirement +/- 1 mod 8 gives 16 residue classes mod 120, which is those 16 Prime95 uses:
1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119

Your idea gives 20 residue classes mod 120:
1,7,17,23,25,31,41,47,49,55,65,71,73,79,89,95,97,103,113,119
so what Prime95 already uses is more efficient.
okay well can we alter it all to make it even more efficient ?

I know now that it eliminates the multiples of 5 I still must try and figure this out lol.

doh dah multiples of 5 still god can i get any dumber lol.

Last fiddled with by science_man_88 on 2010-11-04 at 17:52
science_man_88 is offline  
Old 2010-11-04, 22:07   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default another theory

I have another theory could the p for mersenne primes be the minimum prime p such that x^pn-1 - x^pn-1-1 is divisible by 6 for some set of x values? it seems to work for x=2 and x=3 so far that I've done. I forgot that p=3 and 2 don't work for x=2 lol but does it work for some set for p>3

Last fiddled with by science_man_88 on 2010-11-04 at 22:10
science_man_88 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Mersenne primes and class field theory Nick Math 4 2017-04-01 16:26
Basic Number Theory 11: Gaussian primes Nick Number Theory Discussion Group 0 2016-12-03 11:42
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 08:53.

Sun Sep 20 08:53:48 UTC 2020 up 10 days, 6:04, 0 users, load averages: 1.69, 1.37, 1.44

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.