20031003, 13:55  #1 
Aug 2003
Snicker, AL
3BF_{16} Posts 
Factors of Mersenne numbers ?
Where Mp is a mersenne number calculated as (2^p)1 and p is a prime number.
The factors of Mp must be in the form of q = 2kp+1. where k is an integer greater than 0 and 2kp+1 < sqrt(Mp). Is it always true that if q is a factor of Mp then q is prime? Also, I've noticed the exclusion of potential factors where mod 3 or mod 5 = 0. Why not mod 7 or mod 11 = 0? Fusion 
20031003, 15:50  #2  
"William"
May 2003
New Haven
2^{6}·37 Posts 
Re: Factors of Mersenne numbers ?
Quote:
4stp^2+2sp+2st+1 =2(2stp+s+t)p+1 Let r=2stp+s+t, and we have a composite factor 2rp+1 

20031004, 16:31  #3 
Aug 2003
Snicker, AL
7×137 Posts 
Wblipp,
I'm trying to get to the bottom of a question re factors of Mersenne numbers. Here is the gist of what I think you showed mathematically. The factors of a Mersenne number must be of the form 2kp+1. However, a given factor may be some multiple of (2kp+1) such that it can be factored to the smaller 2kp+1 value. For a given exponent, (19 in this case) the potential factors can be calculated as below. 2*1*19 + 1 = 39 2*2*19 + 1 = 77 2*3*19 + 1 = 115 2*4*19 + 1 = 153 2*5*19 + 1 = 191 2*6*19 + 1 = 229 2*7*19 + 1 = 267 2*8*19 + 1 = 305 2*9*19 + 1 = 343 2*10*19 + 1 = 381 2*11*19 + 1 = 419 2*12*19 + 1 = 457 2*13*19 + 1 = 495 2*14*19 + 1 = 533 2*15*19 + 1 = 571 2*16*19 + 1 = 609 2*17*19 + 1 = 647 2*18*19 + 1 = 685 2*19*19 + 1 = 723 You then trial divide the Mp value (524287) by each of the potential divisors. If the Mp is not prime, then one of the values tested will evenly divide the Mp. Now to me, this means you can eliminate certain of the potential divisors. I simply check that each potential factor is not prime for some divisor less than the 2*1*p + 1 value and that each potential divisor less than the sqrt(Mp) is not evenly divisible by the 2*1*p + 1 value. Based on this, the only divisors I have to try are: 191, 229, 419, 457, 571, and 647. This cuts the original list of 19 possible divisors down to just 6. This is not quite all but most of what I see in a spreadsheet I've built to analyze Mp numbers. Admittedly it is limited to relatively small values but it does show a couple of very interesting relationships. One of the relationships is very specific to a Mp number that is prime and can be tested for using very small values of 2kp+1! Fusion 
20031004, 18:09  #4  
"Patrik Johansson"
Aug 2002
Uppsala, Sweden
5^{2}·17 Posts 
I think this is used in Prime95:
From http://www.mersenne.org/math.htm Quote:


20031005, 21:16  #5 
Aug 2003
Snicker, AL
959_{10} Posts 
I found the answers I was after with just a bit of digging.
1. Factors of Mersenne numbers should always be prime except in a very rare case where one value of 2kp+1 is evenly divisible by another value of 2kp+1. (I have not investigated whether or not the exception can even occur.) 2. I was way off base on the mod 3 and mod 5 part. Look at the math, its pretty simple. Now I'll ask a much more complex question. Per George's description of factoring, 95% of all potential factors can be eliminated by screening. By direct calculation, the number of potential factors grows rapidly. Here is a table listing a prime exponent (some of which yield prime and others composite mersenne numbers) and the number of potential factors where only numbers less than or equal to the square root of Mp are considered. exponent : number of potental factors 7:0 11:2 13:3 17:10 19:19 23:62 29:399 As you can see, the potential factors grow at an "exponential" rate. Is there a simple formula to predict the number of potential factors of a given mersenne number (calculated as 2^p1)? A direct consequence of the above would seem to be that as prime95 tests progressively larger numbers its potential to find factors is constantly decreasing. Even though you can factor to a greater bit depth because the prime exponent is progressively larger, the number of potential factors is increasing which means the percentage of factors prime95 can realistically test is constantly shrinking. Ergo there will be a point reached where factoring is almost totally ineffective! 
20031006, 22:17  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:
From some points of view, Prime95's "potential" to find factors is nondecreasing. Trial division is a valid method for any size of number, mathematically speaking. Now, there is an upper limit on the size of number than Prime95 can handle, but that could be raised with more programming work. In fact, for large enough exponents, it becomes impossible to perform a LucasLehmer test in a time less than the age of the known universe, but it is still feasible to perform a certain amount of trial factoring, with a small but nonzero probability of finding a factor. See the "Catalan sequence (is C5 prime?)" thread elsewhere in this Math forum at http://mersenneforum.org/showthread....&threadid=1073 In terms of the absolute size of the interval in which potential factors are tested, trial factoring becomes "faster" as the Mersenne exponents become larger. Last fiddled with by cheesehead on 20031006 at 22:20 

20031007, 20:08  #7 
Aug 2003
Snicker, AL
1110111111_{2} Posts 
Cheesehead,
Agree that factoring can be performed even on numbers so large that LL tests are impractical. My point is that even though the probability of finding a factor is nonzero, the number of tests that can be performed is finite and the percentages for finding a factor decrease because of that limit. Your definition of "faster" is to reach a greater bit depth with fewer factoring iterations. My definition of faster would be to be able to perform more factoring iterations in the same time period. Granted that technology is advancing and we will have better computers tomorrow than today, there is still a theoretical limit to exponent size that can be tested. One of the consequences of the numbers I have been evaluating is that I now know more about why Mp's are so scattered. t=log2(log2(Mn)) is a poor gap predictor! If I've got my numbers correct, the linearity of the first 38 Mersenne primes will become much less linear as number size increases. I've even decided to come up with my own special creation (tongue in cheek of course). I call it the Theoretical Mersenne Prime. Its a theoretical number such that it precisely falls into the gap in the poisson process. We'll treat it like the (sqrt 1) and give it a special letter of the alphabet so we can perform arithmetic operations with it. Fusion (there is actually somthing to be said about treating an unknown Mp as a theoretical number) 
20031021, 23:07  #8 
Aug 2003
Snicker, AL
7×137 Posts 
Ok, so this is an oddball observation and may not have much applicability. Nonetheless its an interesting observation.
Given a mersenne number Mp, extract the integer square root that is less than Mp. Square the root sqrt(Mp) * sqrt(Mp) and subtract that value from Mp. Now see if the remainder is evenly divisible by the original prime. Here is an example: 2^111 is 2047 sqrt(2047) is 45 45*45 is 2025 2047  2025 is 22 22 is evenly divisible by 11 therefore 2^111 is composite. Please note that there are prime exponents that do not follow this, for example 2^231. However, it does seem to work for some significant number of potential of Mp's. Fusion 
20031026, 06:01  #9 
Aug 2003
Snicker, AL
7×137 Posts 
I checked out the above item re the remainder being evenly divisible by the prime. It only holds true for small exponents. By the time it gets to significant exponents, its completely useless.
Here is a Ubasic program that demonstrates it pretty well. Note, its limited to exponents below about 5000. 10 A=43 20 B=2^A1 30 C=int(sqrt(B)) 40 D=C+int((B(C*C))/C) 50 E=B(C*D) 55 print int(E/A),(E@A):print:print If you want to turn the above into a general factoring routine, here are the changes: 20 B=123456 rem set B = any number 30 C=int(sqrt(B)) 40 D=C+int((B(C*C))/C) 50 E=B(C*D) 60 if E=0 then print C,D 70 for X=C to 2 step 1 80 C=C1 90 F=D+int((D+E)/C) 100 E=(D+E)@C 110 D=F 120 if E=0 then print C,D 130 next X Note that this factoring algorithm is NOT optimized for 2kp+1 factors of Mersenne numbers. Fusion 
20031026, 13:21  #10 
Sep 2002
2×331 Posts 
Is UBasic capable of dealing with integers to 72 bits ( I guess 145 after a multiply of two 72 bit numbers followed by a * 2) ?
Or a full mod of a 79 million bit number ? Are there some special mathematical routines that allow very efficient mod calculations ? I am trying to write routines to do integer functions in greater than 64 bits (a thousand bits potentially) in MASM and/or Delphi, and would like to check my work. I realize prime95 has optimized MASM code to do the powering algorithm to 72 bits. I am interested in trial factoring routines and algorithms without using any Floating Point instructions. I haven't really considered using any of integer MMX(+), 3DNow(+), SSE, SSE2 instructions because I haven't done any work with them and may have limited programming access to them. Without using any floating point it would allow another FP intensive program ( LL ) to run concurrently without contention with math units. If I code some good routines I'll post them. (If they are good enough maybe they could go into prime95 ) 
20031026, 15:46  #11  
Sep 2003
5×11×47 Posts 
Quote:
Trialfactoring already doesn't use floating point (but trialP1factoring does). See this thread and this thread. On a hyperthreading CPU, you can run trialfactoring and LL testing simultaneously. For integer functions in greater than 64 bits, if you're using Linux, you can check out the source code to the opensource GMP library for ideas. See for instance this source code for verifying Mersenne factors: http://www.mersenneforum.org/showthr...2917#post12917 It calls a specialpurpose GMP function for calculating a^{b} mod c. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
Modular restrictions on factors of Mersenne numbers  siegert81  Math  23  20140318 11:50 
Mersenne prime factors of very large numbers  devarajkandadai  Miscellaneous Math  15  20120529 13:18 
Mersenne Prime Factors of v.large numbers  devarajkandadai  Miscellaneous Math  6  20060104 22:44 
Factors of Mersenne Numbers  asdf  Math  17  20040724 14:00 