Test Lucasa-Lehmera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 p 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 n bity spośród k plus pozostałe bity k, są równoważne k modulo 2n−1. Równoważność może być stosowana powtarzalnie do momentu co najwyżej n bitów reszty. W tym postępowaniu, reszta po wykonaniu dzielenia k przez liczbę Mersenne’a 2n−1 jest obliczona bez używania dzielenia. Na przykład:

916 mod 25−1 = 11100101002 mod 25−1
= 111002 + 101002 mod 25−1
= 1100002 mod 25−1
= 12 + 100002 mod 25−1
= 100012 mod 25−1
= 100012
= 17.

Ponadto, ponieważ s × s nigdy nie przekroczy M2 < 22p, ta prosta technika zbiega w co najwyżej 1 p-bitowy dodatku (ewentualnie przeprowadza z p-tego bitu w pierwszy bit), co może być wykonane w liniowym czasie. Algorytm ten posiada wyjątkowy przypadek. Daje 2n−1 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 s 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ść s wynosi 0, wnioskujemy, że M3 jest pierwsza.

Z drugiej strony, M11 = 2047 = 23 × 89 nie jest pierwsza. Powtórnie, s 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ść s nie jest równa  0, wnioskujemy, że M11 = 2047 nie jest pierwsza. Mimo, że M11 = 2047 posiada nietrywialne czynniki, test Lucasa–Lehmera test 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 Mp 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:

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

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]

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. Właśnie przy jego użyciu znaleziono największe 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 wielkie liczby naturalne jak s 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]

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 około 12 godzin na komputerze osobistym z procesorem o częstości kilku Gigaherców): Funkcja Mod[s, M] zwraca na końcu 0 jedynie jeśli jest liczbą pierwszą.

M = 2^859433 - 1;
s = 4;
Do[temp = PrintTemporary[n]; s = Mod[s*s - 2, M];  NotebookDelete[temp], {n, 1, 859433 - 2}];
Print[Mod[s, M]]

Zobacz też[edytuj]

Uwagi[edytuj]

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

Przypisy

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

Linki zewnętrzne[edytuj]