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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.