Evaluating 2^k steps takes O(k) multiplications when done using a fast exponentiation algorithm. Even assuming O(n^2) multiplication and O(n) prime divisors, c

Evaluating 2^k steps takes O(k) multiplications when done using a fast exponentiation algorithm. Even assuming O(n^2) multiplication and O(n) prime divisors, checking a single candidate shouldn't take more than O(n^4). I'm sure that in reality you can do much better, probably significantly under O(n^3), e.g. because there are fewer prime factors, using a faster multiplication algorithm, and by reusing intermediate results during the exponentiations. Factoring 2^n-1 can be done once for a given n in O(2^(n/4)), so it is not the bottleneck. There are also probably quite a lot of checks that can quickly rule out lots of values without having to give them to the heavy machinery. In the end I expect the total running time to be O(2^n * n^2) or so.