Test Lucasa-Lehmera
Z Wikipedii
Test Lucasa-Lehmera – test pierwszości dla liczb Mersenne'a.
Niech Mp oznacza liczbę Mersenne'a Mp = 2p − 1 dla pewnej nieparzystej liczby pierwszej p (tzn. liczby pierwszej większej od 2). Definiuje się następujący ciąg liczb naturalnych (Sk):
Test Lucasa-Lehmera orzeka, że liczba Mp 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 Sp − 2 przez Mp nazywa się residuum Lucasa-Lehmera liczby p. Istotę testu można zatem streścić sformułowaniem:
- liczba Mersenna Mp 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.
