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
About this result
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