20101103, 15:38  #1  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
theory on Mersenne primes ?
Quote:


20101103, 16:12  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
1000010101011_{2} Posts 
Note that all primes above 3 are either 1 or 5 mod 6.
Quote:
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. 

20101103, 16:30  #3  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:


20101103, 16:43  #4  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:
I don't see any way this can be an improvement on current methods. Last fiddled with by MiniGeek on 20101103 at 16:46 

20101103, 17:10  #5 
Aug 2006
2×2,969 Posts 
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. 
20101103, 17:17  #6 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
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 6n1 since 11= 5 mod 6 6n+1 k=0,3,6,9, (3x+0) 6n1 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. 
20101103, 17:25  #7  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17×251 Posts 
Quote:
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 MiniGeek on 20101103 at 17:34 

20101103, 17:39  #8  
Aug 2006
2×2,969 Posts 
Quote:


20101104, 16:37  #9 
Einyen
Dec 2003
Denmark
5646_{8} Posts 
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 coprime 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. 
20101104, 17:03  #10  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
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 20101104 at 17:52 

20101104, 22:07  #11 
"Forget I exist"
Jul 2009
Dumbassville
20261_{8} Posts 
another theory
I have another theory could the p for mersenne primes be the minimum prime p such that x^p_{n}1  x^p_{n1}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 20101104 at 22:10 
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  20170810 13:47 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
Mersenne primes and class field theory  Nick  Math  4  20170401 16:26 
Basic Number Theory 11: Gaussian primes  Nick  Number Theory Discussion Group  0  20161203 11:42 
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods  optim  PrimeNet  13  20040709 13:51 