Factors of Mersenne numbers ?

[Fusion_power]

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

[wblipp]

Originally posted by Fusion_power
The factors of Mp must be in the form of q = 2kp+1.

Is it always true that if q is a factor of Mp then q is prime?

Take two prime factors, say 2sp+1 and 2tp+1, and multiply them together. The result is
4stp^2+2sp+2st+1
=2(2stp+s+t)p+1

Let r=2stp+s+t, and we have a composite factor 2rp+1

[Fusion_power]

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

[patrik]

I think this is used in Prime95:
From http://www.mersenne.org/math.htm

The GIMPS factoring code creates a modified sieve of Eratosthenes with each bit representing a potential 2kp+1 factor. The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so. Also, bits representing potential factors of 3 or 5 mod 8 are cleared. This process eliminates roughly 95% of potential factors.

[Fusion_power]

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^p-1)?


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!

[cheesehead]

Originally posted by Fusion_power

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.)

Any Mersenne number which has three or more prime factors necessarily also has three or more composite proper factors, each of which is a product of two or more (but not all) of the prime factors. :)

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!

Well, that depends on the definitions of "potential", "realistically", and "ineffective" one is using. :)

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 Lucas-Lehmer 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.

[Fusion_power]

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 non-zero, 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)

[Fusion_power]

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^11-1 is 2047
sqrt(2047) is 45
45*45 is 2025
2047 - 2025 is 22

22 is evenly divisible by 11 therefore 2^11-1 is composite.


Please note that there are prime exponents that do not follow this, for example 2^23-1. However, it does seem to work for some significant number of potential of Mp's.

Fusion

[Fusion_power]

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^A-1
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=C-1
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

[dsouza123]

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 )

[GP2]

Originally posted by dsouza123
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 am interested in trial factoring routines and algorithms without using any Floating Point instructions.

Trial-factoring already doesn't use floating point (but trial-P-1-factoring does). See this thread and this thread. On a hyperthreading CPU, you can run trial-factoring 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 open-source GMP library for ideas.

See for instance this source code for verifying Mersenne factors:
http://www.mersenneforum.org/showthr...2917#post12917
It calls a special-purpose GMP function for calculating a^b mod c.