Przejdź do zawartości

Test Lucasa-Lehmera

Z Wikipedii, wolnej encyklopedii

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

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, rząd dzieli , jednak więc nie dzieli on . Wobec tego rząd 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 | 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 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 | 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[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 | 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.) 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 | edytuj kod]

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