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.