1
$\begingroup$

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 :

enter image description here

My question : Why this test is considered to be less practical than Lucas-Lehmer primality test ?

  • 1
    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.2012-01-04

1 Answers 1

4

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.

  • 0
    ah you answered as I was typing my answer :D2012-01-04