Well, this blog has basically been left inactive for quite a while. I decided I’d start using it again… but in a different way.
As some may be aware, I’m a mathematician (actually, Mathematical physicist, but I’m also big on pure Mathematics). So I’m going to turn this blog into a mathematical blog. Sorry to those who severely dislike mathematics… but you should really get over it, maths is fun.
Anyway, this post will cover some thoughts I’ve had regarding the Mersenne Prime search.
What is the Mersenne Prime search? It’s a search for primes of the form , where
is a prime number (if p isn’t prime, then
cannot be prime). Numbers of that form are known to be prime for
– but it’s not true for all primes
by any means. So that’s where the “searching” comes into it.
The common method of testing Mersenne numbers to see if they are prime is to use what is called the “lucas-lehmer test”, which is relatively fast, but still extremely slow when you get larger powers. It is also incapable of determining any factors of the number if it is composite. To date, we know of less than 50 Mersenne Primes. But I think it is possible to come up with a faster prime-test algorithm. And here’s a thought I’ve been having.
Mersenne numbers with prime powers can only even have factors of the form , with
and
being equivalent to the trivial factors 1 and
. This gives us a hint as to how to test for factors. But it’s not quite enough.
Suppose that n is a factor of . Then
for all values of “a”. This is because
. This fact can be used to derive a number of interesting results. What is notable immediately is that if either n+a or a is a multiple of 2, you can divide that number by 2 and not change the result of the gcd operation – this is because applying
in the second part of the gcd doesn’t change the result of the gcd.
One choice of a that is interesting is , which, assuming that
, allows us to conclude that
. But we can go further – if the difference between m and q is a power of 2 (that is,
), then
, because of the aforementioned
rule. Because q is an arbitrary number we have chosen, anyway, the requirement that
is easily satisfied by choosing
.
What this means is that q can be chosen to be the distance between m and the nearest power of 2 to m. For instance, if p=41, the smallest m (not counting m=0) is m=163. For this value of m, the smallest q is q = 163 – 128 = 35. But in testing q=35, you automatically are also checking m = 36, 37, 39, 43, 51, 67, 99, 291, 547… and so on. And so, a greater number of factors are tested at the same time. This advantage is good for smaller values of q, but as q increases, the number of factors being tested shrinks. Thus, more needs to be done.
Another step that can be taken is to note that p is not a factor of , and thus can be divided out of the right hand side. This gives, using
under the gcd, the conclusion that (put on the next line for clarity):
There are a number of advantages to this form – for one, doesn’t have to be calculated. For another, rather than having to multiply numbers for each q, one only has to add them, before raising to the given power. It also shows us an interesting formula – if we choose q such that
, then n is equal to
. And this will be true for any integer j. Note that n hasn’t changed throughout this consideration, so one can propagate this conclusion back throughout the sequence. However, this conclusion isn’t useful, as it is true whether
is prime or not, and doesn’t determine any factors.
To demonstrate this approach in action, consider p=29. For this number, . The value
. Now, as it so happens, the smallest m for this number is m=4, which is a power of 2, and thus can be found with q=0. So we test like this:
This is equal to gcd(536870911,k) where k is of the order of , and thus won’t be actually included here. But what I can say is that
, and therefore, the gcd(536870911,k) = 233. 233 is a prime factor of 536870911 (in fact, 233 = 2*29*4 + 1, just as I said – the m = 4). Interestingly, if one uses q=3, one actually gets the product of TWO factors out, of the three prime factors of the number. This is because the second m value is m=19 = 16+3, while the first one is m=4 = 1 + 3. And so, the gcd ends up being 233*1103 = 256999.
Now, there are avenues of investigation I still have, to try to further refine the approach. For instance, if and
are both m-values for factors of a prime number, then
. This fact may be of value, in conjunction with the aforementioned gcd considerations, to further narrow the number of situations requiring testing.