Test Lucasa-Lehmera

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Test Lucasa-Lehmera – test pierwszości dla liczb Mersenne’a. Test ten został wymyślony 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 p można sprawdzić za pomocą prostego algorytmu podziału, gdzie p jest wykładniczo mniejsze 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 OEIS).

Test Lucasa-Lehmera orzeka, że liczba 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 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)
    var s = 4
    var M = 2p − 1
    repeat p − 2 razy:
        s = ((s × s) − 2) mod M
    if s == 0 return PIERWSZA else return ZŁOŻONA

Działanie mod M w każdej iteracji zapewnia, że wszystkie pośrednie wyniki są co najwyżej -bitowe (w innym przypadku liczba bitów byłaby dublowana w każdej iteracji).

Złożoność czasowa[edytuj | edytuj kod]

W powyższym algorytmie, podczas każdej iteracji wykonywane są dwie kosztowne operacje: mnożenie s × s, i operacja modulo mod M. Operacja mod M może być wykonywana szczególnie efektywnie na standardowych dwójkowych systemach, poprzez dokonanie następującej obserwacji

Mówi ona, że najmniej znaczące bity spośród plus pozostałe bity są równoważne modulo Równoważność może być stosowana powtarzalnie do momentu co najwyżej bitów reszty. W tym postępowaniu, reszta po wykonaniu dzielenia przez liczbę Mersenne’a jest obliczona bez używania dzielenia. Na przykład:

Ponadto, ponieważ s × s nigdy nie przekroczy M2 < 22p, ta prosta technika zbiega w co najwyżej 1 -bitowy dodatku (ewentualnie przeprowadza z -tego bitu w pierwszy bit), co może być wykonane w liniowym czasie. Algorytm ten posiada wyjątkowy przypadek. Daje dla mnożenia modulo zamiast poprawnej wartości 0. Jednak, ten przypadek jest łatwy do wykrycia I naprawienia.

Przykłady[edytuj | edytuj kod]

Liczba Mersenne’a M3 = 7 jest pierwsza. Test Lucasa–Lehmera sprawdza to w następujący sposób. Początkowo jest ustalona i równa 4, później jest modyfikowana 3−2 = 1 raz:

  • s ← ((4 × 4) − 2) mod 7 = 0.

Ponieważ końcowa wartość wynosi 0, wnioskujemy, że M3 jest pierwsza.

Z drugiej strony, M11 = 2047 = 23 × 89 nie jest pierwsza. Powtórnie, jest ustalona i równa 4, ale teraz jest modyfikowana 11−2 = 9 razy:

  • s ← ((4 × 4) − 2) mod 2047 = 14
  • s ← ((14 × 14) − 2) mod 2047 = 194
  • s ← ((194 × 194) − 2) mod 2047 = 788
  • s ← ((788 × 788) − 2) mod 2047 = 701
  • s ← ((701 × 701) − 2) mod 2047 = 119
  • s ← ((119 × 119) − 2) mod 2047 = 1877
  • s ← ((1877 × 1877) − 2) mod 2047 = 240
  • s ← ((240 × 240) − 2) mod 2047 = 282
  • s ← ((282 × 282) − 2) mod 2047 = 1736

Ponieważ końcowa wartość nie jest równa  0, wnioskujemy, że M11 = 2047 nie jest pierwsza. Mimo że M11 = 2047 posiada nietrywialne czynniki, test Lucasa–Lehmera nie daje żadnych wskazówek jakie mogą one być.

Dowód[edytuj | edytuj kod]

Dowód poprawności testu przedstawiany tutaj jest prostszy niż oryginalny dowód podany przez Lehmera. Przywołajmy definicję

Naszym celem jest pokazanie, że jest pierwsza wtedy i tylko wtedy gdy

Ciąg jest dany rekurencyjnie z rozwiązaniem w jawnej postaci. Niech and Poprzez indukcję dostajemy dla każdego

i

Ostatni krok wykorzystuje Jawna forma jest używana zarówno w dowodzie dostateczności jak I konieczności.

Dostateczność[edytuj | edytuj kod]

Celem jest pokazanie, że implikuje, że jest pierwsza. Bezpośredni dowód wykorzystujący elementarną teorię grup daną przez J. W. Bruce[1] jak nawiązuje Jason Wojciechowski[2].

Przypuśćmy, że Wówczas

dla pewnego całkowitego k, więc

Mnożąc przez otrzymujemy

Zatem

Dla uzyskania sprzeczności, przypuśćmy, że Mp jest złożona, i niech q będzie najmniejszym pierwszym czynnikiem liczby Mp. Liczby Mersenne’a są nieparzyste, więc q > 2. Niech będzie zbiorem liczb całkowitych modulo q, i niech Mnożenie w jest zdefiniowane jak następuje

Oczywiście, to mnożenie jest działaniem wewnętrznym, to znaczy produkt liczb z ''X'' przechodzi w siebie. Rozmiar X oznaczamy przez

Gdy q > 2, i należą do X[note 1]. Podzbiór elementów X z ich odwrotnościami tworzy grupę, którą oznaczamy X*, a jej rząd Jeden z elementów X nie posiada odwrotności, jest to 0, więc

Teraz i więc

w X.

Następnie, wykorzystując równanie (1),

w X, I podnosząc obie strony do kwadratu otrzymujemy

Zatem należy do X* I posiada odwrotność Co więcej ustalony dzieli Jednak więc nie dzieli Przeto, wynosi dokładnie

Rząd elementu jest nie większy niż rząd (rozmiar) grupy, więc

Ale q jest najmniejszym pierwszym czynnikiem rozkładu liczby złożonej więc

To prowadzi do sprzeczności Dlatego jest pierwsza.

Konieczność[edytuj | edytuj kod]

Z drugiej strony, celem jest pokazanie, że pierwszość implikuje Poniższy uproszczony dowód przedstawił Öystein J.R.

Gdy dla nieparzystych z własności symbolu Legendre’a wynika, że To oznacza, że 3 jest podwójnym nieresiduum modulo Dzięki kryterium Eulera, jest to równoważne

Natomiast, 2 jest podwójnym residuum modulo ponadto i stąd Tym razem, kryterium Eulera pozwala napisać

Połączenie tych dwóch równoważnych relacji daje

Niech i zdefiniujmy X tak jak wcześniej jako pierścień Wówczas w pierścieniu X, otrzymujemy

Gdzie pierwsza równość wykorzystuje Dwumian Newtona w skończonej dziedzinie, która przedstawia się

A druga równość wykorzystuje Małe twierdzenie Fermata, które brzmi

dla każdej liczby całkowitej a. Wartość została wybrana tak, aby Co za tym idzie, może być wykorzystana do wyliczenia w pierścieniu X jako

To co pozostaje to mnożenie obu stron równania przez i wykorzystanie co daje

Skoro jest 0 w X, jest również 0 modulo

Zastosowanie[edytuj | edytuj kod]

Test Lucasa–Lehmera jest testem pierwszości używanym przez Great Internet Mersenne Prime Search do znajdowania dużych liczb pierwszych. Te poszukiwania są bardzo owocne i przyczyniły się do znalezienia wielu największych liczb pierwszych znanych dzisiaj[3]. Test jest uważany za wartościowy, ponieważ potrafi zbadać pierwszość olbrzymich liczb zawartych w zbiorach o dużej liczbie elementów w przeciągu przystępnego wymiaru czasu. W odróżnieniu od równie szybkiego testu Pépina dla każdej liczby Fermata, który może być używany jedynie na wiele mniejszych zbiorach tak olbrzymich liczb zanim zakres obliczeniowy się wyczerpie.

Uwagi: test jest bardzo szybki i bardzo prosty. Przy jego użyciu znaleziono największe dotąd znane liczby pierwsze. Test wymaga jak najszybszego algorytmu mnożenia np. szybkiej transformaty Fouriera. Ponieważ mnożenie liczb zapisanych w systemie liczbowym o danej podstawie jest w pewnym sensie splotem funkcji (cyfra jako wartość w funkcji potęgi podstawy) a transformata Fouriera splotu dwóch funkcji jest iloczynem ich transformat, zatem wielkie liczby naturalne jak można mnożyć szybko przez siebie robiąc szybką transformatę Fouriera z ich cyfr, a następnie szybką transformatę odwrotną iloczynu tych transformat.

Kod w Mathematica[edytuj | edytuj kod]

Krótki kod w języku Mathematica (tutaj sprawdzający liczbę pierwszą Mersenne’a Davida Slowinskiego & Paula Gage’a z 4 stycznia, 1994 (znaną 33-cią) z wykładnikiem ) w czasie nieco ponad 2 godzin na komputerze osobistym z procesorem Skylake o częstotliwości 2,9 GHz): Funkcja Mod[s, M] zwraca na końcu 0 jedynie jeśli jest liczbą pierwszą.

M = 2^859433 - 1;
s = 4;
AbsoluteTiming[
 Monitor[Do[
   s = Mod[s*s - 2, M], {n, 1, 859433 - 2}], {ProgressIndicator[
    n, {1, 859433 - 2}], n}]];
Print[Mod[s, M]]

Zobacz też[edytuj | edytuj kod]

Uwagi[edytuj | edytuj kod]

  1. Formalnie, i należą do X. Poprzez nadużycia językowe and są identyfikowane z ich obrazami w X zgodnie z naturalnym pierścieniem homomorfizmu z w X, który przyporządkowuje dla T.

Przypisy[edytuj | edytuj kod]

  1. J.W. Bruce, A Really Trivial Proof of the Lucas–Lehmer Test, „The American Mathematical Monthly”, 4 (100), 1993, s. 370–371, DOI10.2307/2324959, JSTOR2324959.
  2. Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.
  3. The „Top Ten” Record Primes, The Prime Pages.

Linki zewnętrzne[edytuj | edytuj kod]