# An alternative way to test primality of Mersenne numbers?

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 ?

-
If you are going to loop $x$ from $1$ to $\sqrt{2^p-1}$, why not just check if $x$ is factor? –  Thomas Andrews Jan 4 '12 at 14:40
Your test is closely related to the so-called Fermat primality test, which does the same thing with $x^2+y^2$. The Fermat test can be pretty good at detecting nonprimes $n$ which can be expressed as $n=ab$ where $a$ and $b$ are close to each other. But its bad case running times are very large. –  André Nicolas Jan 4 '12 at 14:47

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.