Test Lucasa-Lehmera – test pierwszości dla liczb Mersenne’a. Test został ułożony przez Edwarda Lucasa w 1856, a następnie ulepszony przez niego w 1878. W 1930 test został zmodyfikowany przez Derricka Henry’ego Lehmera.
Niech oznacza liczbę Mersenne’a dla pewnej nieparzystej liczby pierwszej (tzn. liczby pierwszej większej od 2). Pierwszość liczby można sprawdzić za pomocą prostego algorytmu podziału, gdzie jest wykładniczo mniejsza od Definiuje się następujący ciąg liczb naturalnych
Oto kilka początkowych wyrazów tego ciągu: 4, 14, 194, 37634, ... (ciąg A003010 w OEISEncyklopedia ciągów liczb całkowitych w wersji on-line).
Test Lucasa-Lehmera orzeka, że liczba jest pierwsza wtedy i tylko wtedy, gdy jest dzielnikiem wyrazu o numerze w tym ciągu, co krótko zapisuje się kongruencją:
Resztę z dzielenia liczby przez nazywa się residuum Lucasa-Lehmera liczby Istotę testu można zatem streścić sformułowaniem: liczba Mersenna jest pierwsza wtedy i tylko wtedy, gdy residuum Lucasa-Lehmera liczby równe jest zeru.
Za pomocą pseudokodu test można przedstawić w następujący sposób:
// Ustalamy, czy Mp = 2p − 1 jest pierwsza Lucas-Lehmer(p) niech s ← 4 niech M ← 2p − 1 powtórz p − 2 razy: s ← ((s × s) − 2) mod M jeśli s = 0 zwróć PIERWSZA w przeciwnym razie zwróć ZŁOŻONA