**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Lucas–Lehmer primality test

Summary

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.
The test
The Lucas–Lehmer test works as follows. Let Mp = 2p − 1 be the Mersenne number to test with p an odd prime. The primality of p can be efficiently checked with a simple algorithm like trial division since p is exponentially smaller than Mp. Define a sequence {s_i} for all i ≥ 0 by
:
s_i=
\begin{cases}
4 & \text{if }i=0;
\
s_{i-1}^2-2 & \text{otherwise.}
\end{cases}
The first few terms of this sequence are 4, 14, 194, 37634, ... .
Then Mp is prime if and only if
:s_{p-2} \equiv 0 \pmod{M_p}.
The number sp − 2 mod Mp is called the Lucas–Lehmer residue of p. (Some authors equivalently set s1 = 4 and test sp−1 mod Mp). In pseudocode, the tes

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

Related courses

No results

No results

Related people

Related concepts

Related lectures

No results

No results

No results

Related units

No results