# test for primality of Mersenne numbers

Suppose $p$ is an odd prime, and define a sequence $L_{n}$ recursively as

 $L_{0}=4,\qquad L_{n+1}=(L_{n}^{2}-2)\bmod(2^{p}-1).$

The number $2^{p}-1$ is prime if and only if $L_{p-2}=0$.

## References

• 1 Donald E. Knuth. The Art of Computer Programming, volume 2. Addison-Wesley, 1969.
Title test for primality of Mersenne numbers TestForPrimalityOfMersenneNumbers 2013-03-22 13:39:48 2013-03-22 13:39:48 bbukh (348) bbukh (348) 8 bbukh (348) Algorithm msc 11A41 msc 11Y11 msc 11A51