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

Related people

Related units

Related concepts

Related courses

Related lectures