Fast probablistic Test for Mersenne Prime numbers
3^(2^p) = 9 mod Mp
You need only p times squaring and calculating mod Mp.
Besides you can do a Fourier transformation to speed up the squaring.
This simple test derives dirctly from the little Fermat.