20031229, 17:34  #1 
Aug 2003
Snicker, AL
2^{3}×3×5^{2} Posts 
Interesting observation re 2kp+1 numbers
So take a mersenne number such as 2^171 which yields 131071
Find all the potential factors of form 2kp+1 1 35 69 103 137 171 205 239 273 307 341 Now divide the number by a 2kp value. Note the +1 is NOT used. 131071/340 = 385 with a remainder of 171. Anybody see something strange about that remainder? Lets do it again. 131071/204 = 642 with remainder 103. Anything ring bells yet? Now I check the valid 2kp+1 values for 2^171 and find that 103, 137, 239, and 307 are the only valid 2kp+1 numbers and result from k values of 3, 4, 7, and 9. The mod results of testing these 4 numbers are: 1, 103, 171, and 103. Fusion Last fiddled with by Fusion_power on 20031229 at 17:42 
20031229, 19:44  #2 
Sep 2002
2·331 Posts 
What does
and find that 103, 137, 239, and 307 are the only valid 2kp+1 numbers mean ? In what sense are they valid and the others in the list (1..341) invalid ? The mod results (131071 mod 2kp) had values (some duplicates) of 1, 35, 103, 171, 239 so if that has anything connection with the validity why is 137 in the valid list and 35,171 missing ? 131071 is prime anyway so only itself and 1 are factors. Though there are more numbers 2kp+1 that goto 131071, 341 is the largest less than the square root of 131071. 
20031229, 20:14  #3 
Dec 2003
Belgium
5×13 Posts 
Fermat's little theorem gives:
2^p=2modp 2^p  2=0modp 2^p  2=2pm 2^p  2=p(2k + 2k') (with m=k + k', choose k'<k) 2^p  1=2pk + 2pk' + 1 2^p  1mod(2kp)=2pk' + 1 So your observations are correct, every mersennenumber with prime exponent has a remainder of the form 2pk'+1 when you divide by 2kp. michael Last fiddled with by michael on 20031229 at 20:19 
20031230, 01:40  #4 
Aug 2003
Snicker, AL
2^{3}×3×5^{2} Posts 
Dsouza,
Any potential factor of a Mp must be a prime number and not 3 or 5 mod 8. See http://www.utm.edu/research/primes/n...fs/MerDiv.html and http://www.mersenne.org/math.htm Based on this you can eliminate 35 since it is divisible by 5, 171 is divisible by 3, etc. This example is a very small Mp, so all are easily verified as prime or composite. Fusion 
20031230, 03:41  #5 
Sep 2002
2×331 Posts 
Thanks for the explanation Fusion_power.
So the valid numbers are the 2kp+1 potential factors that are Prime and when mod 8 are not 3 and not 5. I verified the numbers you listed, 307 even though it is prime, it is 3 when mod 8. So the list is a little shorter. In the Prime95 help file under math it mentioned the valid factors are 1 or 7 mod 8. I guess the quickest with the 2kp+1 is to mod by 8, if the result is 1 or 7 then test it (2kp+1) for primality. At this point test it, using the powering algorithm or powmod or integer division with remainder. If a 2kp+1 potential factor is 1 or 7 mod 8 and prime will it always be a true factor ? Those two test are necessary (I believe) but are they sufficient ? 
20031230, 15:35  #6 
Aug 2003
Snicker, AL
2^{3}·3·5^{2} Posts 
Dsouza,
The sequence of verification is worth discussing. From a computational perspective, is it faster to determine if a number is prime or to determine if it is valid as 1 or 7 mod 8. From George's description, I think he first determines if a number is prime and then does the mod 8 verification. This might be faster if done the other way around. Fusion 
20031230, 15:46  #7  
∂^{2}ω=0
Sep 2002
República de California
10011001101010_{2} Posts 
Quote:
http://www.mersenneforum.org/showthr...&threadid=1736 The fact that any factor q of M(p) must have from j*p+1 comes from some basic properties of multiplicative groups. The fact that the multiplier j must be even (i.e. j = 2*k) is a simple consequence of q having to be odd. The q == +1 mod 8 requirement comes from the theory of quadratic residues. Here's that argument: From the form of N = 2^p  1, we have that 2^p == 1 (mod N). Multiplying by 2, we see that 2^(p+1) == 2 (mod N). Since p is odd (primality of p is not crucial here, just oddness), the LHS is an even power of 2, hence a perfect square, which implies that 2 is a QR mod N, and thus also a QR mod any factor q of N. That immediately implies that q == +1 (mod 8), i.e. that any factor q must be of the form 8*n + 1. This does not change the form of k appearing in factors, but eliminates half of the k's that pass the multipleofsmallprime sieve that is typically used in sieving programs. Quote:
Last fiddled with by ewmayer on 20031230 at 15:47 

20031230, 17:00  #8 
Aug 2003
Snicker, AL
2^{3}×3×5^{2} Posts 
Ewmayer,
So in simple terms, factoring by trial division retains its efficiency no matter how large the exponent because the increasing number of potential factors is countered by the reduced number that are prime and yield 1 or 7 mod 8. Prime95 uses trial division to test for small factors. It uses p1 factoring which also tests for small factors. It then uses p1 with upper and lower bounds to test for small to midsize factors. This begs a few questions. Why does it not also implement p+1 factoring? Also, could Elliptic Curve be used to any advantage with Mp numbers? Fusion 
20031230, 17:25  #9  
Nov 2003
3×5×11 Posts 
Quote:
As a side note, if anyone could point me to a good book on Elliptic Curve factoring, it would be much appreciated. 

20031230, 18:37  #10 
Aug 2003
Snicker, AL
2^{3}×3×5^{2} Posts 
Nfortino,
I've studied the p1 form and p+1 form and they seem to be yin and yang of the same basic group ordering mechanism. Both fail if P + or  1 yield large primes. The example I am looking at shows (p1)/4 and (p+1)/6 where p=29 yielding primes of 7 and 5 respectively. I am looking at a copy of Peter L. Montgomery's A Survey of Modern Integer Factorization Algorithms. Its available as a ghostscript document. I don't have the link currently but it is here on the forum, probably buried several pages back. ECM appears to be modifiable based on division by 2kp to handle Mp numbers. This is just a superficial look but should be possible. Fusion 
20031230, 19:20  #11 
Aug 2003
Snicker, AL
1130_{8} Posts 
I got a partial answer on the question about sequence to determine which numbers 2kp+1 numbers are viable, i.e. verify if the number is prime first or verify if the number yields 1 or 7 mod 8.
Should always do the 1 or 7 mod 8 test first. Why? Simple, 2kp+1 numbers ALWAYS follow a simple pattern. Here is an example for 2^311: 1 1 63 7 125 5 187 3 249 1 311 7 373 5 435 3 497 1 559 7 621 5 683 3 745 1 807 7 869 5 931 3 993 1 1055 7 1117 5 1179 3 1241 1 1303 7 1365 5 1427 3 1489 1 1551 7 1613 5 1675 3 1737 1 1799 7 1861 5 1923 3 1985 1 All you have to do to test for 1 or 7 mod 8 is test the very first number then keep 2 and toss the next 2. Fusion 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
An observation  xilman  Lounge  1  20160807 20:32 
Random observation  jnml  Miscellaneous Math  9  20140428 20:43 
Mersenne Observation....  petrw1  Math  5  20081104 20:27 
Interesting observation  MooooMoo  Lounge  15  20061114 03:40 
Some interesting bandwidth numbers...  Xyzzy  Hardware  0  20030821 21:29 