[AdmSmith]

Fortunately, no full factorization is needed, just a small test factorization up to about 40 000, then the Pollard's (P-1) method and finally Lucas-Lehmer Primality Testing. It is explained here http://www.mersenne.org/various/math.php

But, it is truly amazing.

[zeugma]

it helps quite a bit from what I understand, that Mersenne numbers are of a specialized form. Apparently there are ways of testing primality that don’t involve brute-force factoring of the number. I don’t know if all of those tests are always applicable to any large suspected prime, or if they are only useful for numbers of the specified form. i.e., (2^x)-1

The maths are a bit beyond me on this.