I know that $\forall{d,n\in\mathbb{N}}:d|n\implies2^d-1|2^n-1$.

Now, suppose that $n$ is prime - is there any fast algorithm for finding a divisor of $2^n-1$?

By "divisor", I am referring to a non-trivial divisor (i.e., other than $1$ and $2^n-1$).

By "fast", I am referring to something faster than the standard factorization algorithms.

I assume that first we need to check whether or not $2^n-1$ itself is prime.

We can do that in polynomial time (for example, using AKS).

What if $2^n-1$ is not prime? Is there any small set of potential divisors that is sufficient?

A few examples:

  • $2^{11}-1=23\cdot 89$, and $23\equiv 89\equiv1\pmod{11}$
  • $2^{23}-1=47\cdot178481$, and $47\equiv178481\equiv1\pmod{23}$

So perhaps we can just test divisibility with numbers which are congruent to $1\pmod{n}$.

However, I assume that it doesn't always hold. Moreover, even if it was known that $2^n-1$ must be divisible by some $d\equiv1\pmod{n}$, it would still not reduce the time-complexity of any standard factorization algorithm by more than a constant.

Is there any known method for factorizing such numbers?


Those are Mersenne numbers. It is not known whether there is a polynomial time algorithm to factor those. There is a distributed computing project to find Mersenne primes and factors of Mersenne numbers in Mersenne.org. A fast way to check if a Mersenne number is a prime or not is to use Lucas–Lehmer primality test.

| cite | improve this answer | |

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.