# A fast method for factorizing $2^p-1$

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?