3
$\begingroup$

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

$\endgroup$
3

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – kcrisman
    Sep 1, 2015 at 19:56
  • $\begingroup$ Or is this Theorem 3 in en.wikipedia.org/wiki/… - so it should be mod $2q$ ? $\endgroup$
    – kcrisman
    Sep 1, 2015 at 20:02
  • 1
    $\begingroup$ I made a mistake for sure. I meant to say: $p \equiv 1 \pmod q$ . Now fixed. $\endgroup$
    – Tony Reix
    Sep 1, 2015 at 20:37
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Tony Reix
    Sep 1, 2015 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .