Theorem :
If Mersenne number can be uniquely written in the form : $x^2+3 \cdot y^2$ ,
where $\gcd(x,y)=1$ and $x,y \geq 0$ then that number is a prime number .
Primality test for Mersenne numbers written in Maple code :
My question : Why this test is considered to be less practical than Lucas-Lehmer primality test ?
The number of iterations for your algorithm above is $\sqrt{N}$ where $N$ is the number to be tested, so it's no better than simple trial division (trying all the factors up to $\sqrt{N}$ to see if any of them are a divisor). On the other hand, the number of iterations Lucas-Lehmer test is (approximately) $p$ where $N=2^p-1$ is the number to be tested, so it takes only $\log N$ iterations.