test for primality of Mersenne numbers


Suppose p is an odd prime, and define a sequence Ln recursively as

L0=4,Ln+1=(Ln2-2)mod(2p-1).

The number 2p-1 is prime if and only if Lp-2=0.

References

  • 1 DonaldĀ E. Knuth. The Art of Computer Programming, volumeĀ 2. Addison-Wesley, 1969.
Title test for primality of Mersenne numbers
Canonical name TestForPrimalityOfMersenneNumbers
Date of creation 2013-03-22 13:39:48
Last modified on 2013-03-22 13:39:48
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 8
Author bbukh (348)
Entry type Algorithm
Classification msc 11A41
Classification msc 11Y11
Classification msc 11A51