Test Lucasa-Lehmera

test pierwszości liczb Mersenne’a

Test Lucasa-Lehmeratest pierwszości dla liczb Mersenne’a. Test został ułożony 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 można sprawdzić za pomocą prostego algorytmu podziału, gdzie jest wykładniczo mniejsza 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[1]).

Test Lucasa-Lehmera orzeka, że liczba jest pierwsza wtedy i tylko wtedy, gdy jest dzielnikiem wyrazu o numerze 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)
    niech s ← 4
    niech M ← 2p − 1
    powtórz p − 2 razy:
        s ← ((s × s) − 2) mod M
    jeśli s = 0 zwróć PIERWSZA w przeciwnym razie zwróć 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

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

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

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   oraz   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

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

Przypuśćmy, że   Wówczas

 

dla pewnego całkowitego   więc

 

Mnożąc przez   otrzymujemy

 

Zatem

 

Dla uzyskania sprzeczności, przypuśćmy, że   jest złożona, i niech   będzie najmniejszym pierwszym czynnikiem liczby   Liczby Mersenne’a są nieparzyste, więc   Niech   będzie zbiorem liczb całkowitych modulo   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   przechodzi w siebie. Rozmiar   oznaczamy przez  

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

Teraz   i   więc

 

w  

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

 

w   i podnosząc obie strony do kwadratu, otrzymujemy

 

Zatem   należy do   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   jest najmniejszym pierwszym czynnikiem rozkładu liczby złożonej   więc

 

To prowadzi do sprzeczności   Dlatego   jest pierwsza.

Konieczność edytuj

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   tak jak wcześniej jako pierścień   Wówczas w pierścieniu   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   Wartość   została wybrana tak, aby   Co za tym idzie, może być wykorzystana do wyliczenia   w pierścieniu   jako

 

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

 

Skoro   jest 0 w   jest również 0 modulo  

Zastosowanie edytuj

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[4]. 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 można mnożyć szybko przez siebie, robiąc szybką transformatę Fouriera z ich cyfr, a następnie szybką transformatę odwrotną iloczynu tych transformat.

Implementacje edytuj

Kod w Mathematica edytuj

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.) 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]]

Kod w Python edytuj

Przykładowy kod w języku Python 3 wykorzystujący bibliotekę gmpy2, kod zawiera optymalizację dzielenia modulo (patrz wyżej – Złożoność czasowa) oraz monitorowanie pozostałego czasu wykonania (estymowanego).

'''
Dla liczby p > 2, funkcja zwraca True jeżeli 2^p-1 jest pierwsza, w innym razie zwraca False
'''
from gmpy2 import *
from datetime import *

def Lucas_Lehmer(p):
    s = xmpz(4)
    M = xmpz(2 ** p) - 1
    startt = datetime.now()
    for i in range(0, p - 2):
        time_elapsed = datetime.now() - startt
        speed = i / (time_elapsed.total_seconds() + 1)
        remaining = (p - 2 - i) / (speed + 1)
        if i % int(speed + 1) == 0:
            print('Czas pozostały (hh:mm:ss.ms) {} czas wykonywania {}'.format(timedelta(seconds=remaining), time_elapsed))
        if (s.bit_length() <= p):
            # Podstawowa wersja algorytmu dla s o bitach <= p
            s = s * s - 2
            s = f_mod(s, M)
        else:
            # Optymalizacja dla s bitów > p
            s = s * s - 2
            md = s.bit_length() % 2
            right = s.bit_length() // 2 + md
            left = s.bit_length() // 2
            s = s[0:right] + f_mod(s[left:], M)

    if s == 0:
        return True
    else:
        return False

Zobacz też edytuj

Uwagi edytuj

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

Przypisy edytuj

  1. Encyklopedia ciągów liczb całkowitych w wersji on-line
  2. 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.
  3. Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.
  4. The Largest Known Primes – A Summary. The Prime Pages. (ang.).

Linki zewnętrzne edytuj