Test Lucasa-Lehmera

Test Lucasa-Lehmera – test pierwszości dla liczb Mersenne'a.

Niech $M_p$ oznacza liczbę Mersenne'a $M_p=2^p-1$ dla pewnej nieparzystej liczby pierwszej $p$ (tzn. liczby pierwszej większej od 2). Definiuje się następujący ciąg liczb naturalnych $(S_k)$:

$S_k = \begin{cases}4 & \mbox{gdy }k=0 \\ S^2_{k-1} -2 & \mbox{gdy }k\neq 0\end{cases}$

Test Lucasa-Lehmera orzeka, że liczba $M_p$ jest pierwsza wtedy i tylko wtedy, gdy jest dzielnikiem wyrazu o numerze (p-2) w tym ciągu, co krótko zapisuje się kongruencją:

$S_{p-2} \equiv 0\pmod {M_p}.$

Resztę z dzielenia liczby $S_{p-2}$ przez $M_p$ nazywa się residuum Lucasa-Lehmera liczby $p$. Istotę testu można zatem streścić sformułowaniem:

liczba Mersenna $M_p$ jest pierwsza wtedy, i tylko wtedy, gdy residuum Lucasa-Lehmera liczby $p$ równe jest zeru.

Uwagi: test jest bardzo szybki i bardzo prosty. Właśnie przy jego użyciu znaleziono największe liczby pierwsze. Test wymaga jak najszybszego algorytmu mnożenia np. szybkiej transformaty Fouriera.

Zobacz też

• Edouard Lucas
• Derrick Henry Lehmer