More on Mersenne

I wrote this something like a year and a half ago, but I never actually hit the “publish” button. Well, here it is:

I’ve continued to look into the whole Mersenne factoring issue, and I’ve generalised my equations somewhat.

Suppose that and f doesn’t divide . Then, we have

Let and , so that . If we now assume that , then we get that

This is a more general form than seen in the previous post. If we take and , then we get a useful subset:

To see the power of this, consider that, for p=41, m=163. If we take r=0, then q = 35. But if we take r=7, then q=0.

Of course, p=41 is relatively uninteresting, so we look for a harder example. For p=67, m=1445580, and thus the best q = 397004. But if r=337, then q=492. And because 2pr+1 and 2pq+1 are of the same form, you only need to calculate (2pq+1)^p 492 times in total while searching, and when you calculate for q=337, you can reuse the result in testing r=337. There may be further ways to accelerate or simplify the process, too.

Explore posts in the same categories: Mathematics, Prime Numbers