mersenneforum.org theory on Mersenne primes ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2010-11-03, 15:38   #1
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
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)

2010-11-03, 16:12   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

427710 Posts

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.

2010-11-03, 16:30   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Mini-Geek 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.

2010-11-03, 16:43   #4
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

7×13×47 Posts

Quote:
 Originally Posted by science_man_88 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

 2010-11-03, 17:10 #5 CRGreathouse     Aug 2006 3×1,993 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.
 2010-11-03, 17:17 #6 science_man_88     "Forget I exist" Jul 2009 Dumbassville 838410 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 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.
2010-11-03, 17:25   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

7·13·47 Posts

Quote:
 Originally Posted by science_man_88 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

2010-11-03, 17:39   #8
CRGreathouse

Aug 2006

10111010110112 Posts

Quote:
 Originally Posted by Mini-Geek 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.

 2010-11-04, 16:37 #9 ATH Einyen     Dec 2003 Denmark 7·11·43 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 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.
2010-11-04, 17:03   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by ATH 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

 2010-11-04, 22:07 #11 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Nick Math 4 2017-04-01 16:26 Nick Number Theory Discussion Group 0 2016-12-03 11:42 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 11:09.

Wed May 18 11:09:51 UTC 2022 up 34 days, 9:11, 0 users, load averages: 0.93, 1.09, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔