Test Lucasa-Lehmera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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ż[edytuj | edytuj kod]