Is Mersenne primality testing necessarily EXPTIME?

Question

The computational complexity of primality testing is usually specified in relation to the bit length of the number being tested.

However, Mersenne numbers have the special property that the characterizing instance exponent $p$ is exponentially more succinct than the number it signifies. Surprisingly, most of the literature I've found appears to assume a unary representation of $p$ rather than binary.

The Great Internet Mersenne Prime Search, for example, aims to identify very large Mersene primes via an optimized distributed Lucas–Lehmer primality test. GIMPS as a virtual computer has at times ranked among the TOP500 in terms of expended computational capacity.

So is all this distributed computing truly necessary? Do we really need to expand $p$ to its verbose representation to verify its primality?

Or is there still a possibility that primality testing for Mersenne numbers could be decidable in polynomial time in the size of the instance $p$ via some clever certificate tree?

Answer 1

Nothing is impossible. But the problem is that you might want to check whether a 10 million digit number is a prime, but that number is just 2 raised to an 8 digit power, minus 1, so the problem size would be just 8.

For random 10 million digit numbers, the problem size is 10 million. For 10 million digit Mersenne numbers, the problem size is just 8. You can't even write down that number in polynomial time in the problem size. You can't even write it in base 2 in polynomial time, where the number is just a huge string of 1's.