# Efficient algorithm for factorizing Mersenne numbers?

Is there an efficient algorithm (maybe Polynomial-time?) for factorizing Mersenne numbers of the form $2^p - 1$? We can assume that $p$ is a prime because if it is not, then we can reduce the problem to factorizing smaller Mersenne numbers in polynomial time.

I understand that there is a more efficient primality test for Mersenne numbers (Lucas-Lehmer test) which is faster than AKS and Rabin-Miller (in practice at least). But is there any way to take advantage of the knowledge that a number is a Mersenne number to do a full factorization faster, in cases of non-prime Mersenne numbers?

(If you are curious why I am asking the question: I am reading a paper on generation of binary Lyndon words using arithmetic in $\mathbb{Z}_{2^n - 1}$, which involves factorizing $2^n - 1$ first. I am curious how efficient the algorithm can be made in practice.)

• – lhf
Mar 27, 2014 at 1:17
• The Special Number Field Sieve may be the best way to find a factor, but for a complete factorization, I doubt Mersennes are much easier than other large numbers. Mar 31, 2014 at 13:03
• Sep 4, 2015 at 1:46

Prime factors of a Mersenne number $M_q = 2^q-1$, $q$ prime, are $p$ such that: $p\equiv 1 \pmod{2q}$ and $p\equiv \pm 1 \pmod 8$. That helps for quickly finding small factors of big Mersenne numbers.
Also, Mersenne numbers have the following property: $M_q = (8x)^2 - (3qy)^2$ . See: http://tony.reix.free.fr/Mersenne/Mersenne8x3qy.pdf . But not sure it may help.
• This may be naive, but do you mean $p\equiv 1$ mod $M_q$ or mod $q$? I feel like $p\equiv 1$ as stated immediately implies $p\not\mid M_q$... lemme know if I'm just not reading things correctly. Sep 1, 2015 at 19:56
• Or is this Theorem 3 in en.wikipedia.org/wiki/… - so it should be mod $2q$ ? Sep 1, 2015 at 20:02
• I made a mistake for sure. I meant to say: $p \equiv 1 \pmod q$ . Now fixed. Sep 1, 2015 at 20:37
• And thus, in order to be odd, $p\equiv 1 \pmod{2q}$ . Example: $q=11 , M_q=2047, p_1=1+2q=23=-1 \pmod 8, p_2=1+4*2q=89=1 \pmod 8$. Sep 1, 2015 at 20:40