Test Lucasa-Lehmera

Z Wikipedii

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):

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ą:

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.

[edytuj] Zobacz też:

• Edouard Lucas
• Derrick Henry Lehmer
• przegląd zagadnień z zakresu matematyki