# test for primality of Mersenne numbers

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

$${L}_{0}=4,{L}_{n+1}=({L}_{n}^{2}-2)mod({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 |
---|---|

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 |