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 M_p oznacza liczbę Mersenne'a M_p=2^p-1 dla pewnej nieparzystej liczby pierwszej p (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 M_p. Definiuje się następujący ciąg liczb naturalnych (S_k):

S_k = \begin{cases}4 & \mbox{gdy }k=0 \\
  S^2_{k-1} -2 & \mbox{gdy }k\neq 0\end{cases}

Oto kilka początkowych wyrazów tego ciągu: 4, 14, 194, 37634, ... (ciąg A003010 w OEIS).

Test Lucasa-Lehmera orzeka, że liczba M_p jest pierwsza wtedy i tylko wtedy, gdy jest dzielnikiem wyrazu o numerze (p-2) w tym ciągu, co krótko zapisuje się kongruencją:

S_{p-2} \equiv 0\pmod {M_p}.

Resztę z dzielenia liczby S_{p-2} przez M_p nazywa się residuum Lucasa-Lehmera liczby p. Istotę testu można zatem streścić sformułowaniem:

liczba Mersenna M_p jest pierwsza wtedy, i tylko wtedy, gdy residuum Lucasa-Lehmera liczby p 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

k \equiv (k\,\bmod\,2^n) + \lfloor k/2^n \rfloor \pmod{2^n - 1}.

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ę


  s_i=
   \begin{cases}
    4 & \text{gdy }i=0;\\
    s_{i-1}^2-2 & \text{w pozostałych przypadkach.}
   \end{cases}

Naszym celem jest pokazanie, że Mp jest pierwsza wtedy i tylko wtedy gdy s_{p-2} \equiv 0 \pmod{M_p}.

Ciąg {\langle}s_i{\rangle} jest dany rekurencyjnie z rozwiązaniem w jawnej postaci. Niech \omega = 2 + \sqrt{3} and \bar{\omega} = 2 - \sqrt{3}. Poprzez indukcję dostajemy s_i = \omega^{2^i} + \bar{\omega}^{2^i} dla każdego i:

s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = \left(2 + \sqrt{3}\right) + \left(2 - \sqrt{3}\right) = 4

i


\begin{align}
 s_n
 &= s_{n-1}^2 - 2 \\
 &= \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\
 &= \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\
 &= \omega^{2^n} + \bar{\omega}^{2^n}.
\end{align}

Ostatni krok wykorzystuje \omega\bar{\omega} = \left(2 + \sqrt{3}\right) \left(2 - \sqrt{3}\right) = 1. Jawna forma jest używana zarówno w dowodzie dostateczności jak I konieczności.

Dostateczność[edytuj]

Celem jest pokazanie, że s_{p-2} \equiv 0 \pmod{M_p} implikuje, że M_p 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 s_{p-2} \equiv 0 \pmod{M_p}. Wówczas

\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = k M_p

dla pewnego całkowitego k, więc

\omega^{2^{p-2}} = k M_p - \bar{\omega}^{2^{p-2}}.

Mnożąc przez \omega^{2^{p - 2}} otrzymujemy

\left(\omega^{2^{p-2}}\right)^2 = k M_p\omega^{2^{p-2}} - (\omega \bar{\omega})^{2^{p-2}}.

Zatem,

\omega^{2^{p-1}} = k M_p\omega^{2^{p-2}} - 1.\qquad\qquad(1)

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 \mathbb{Z}_q będzie zbiorem liczb całkowitych modulo q, i niech X = \left\{a + b \sqrt{3} \mid a, b \in \mathbb{Z}_q\right\}. Mnożenie w X jest zdefiniowane jak następuje

\left(a + \sqrt{3} b\right) \left(c + \sqrt{3} d\right) = [(a c + 3 b d) \,\bmod\,q] + \sqrt{3} [(a d + b c) \,\bmod\,q].

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

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

Teraz M_p \equiv 0 \pmod{q} i \omega \in X, więc

kM_p\omega^{2^{p-2}} = 0

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

\omega^{2^{p-1}} = -1

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

\omega^{2^p} = 1.

Zatem \omega należy do X* I posiada odwrotność \omega^{2^{p}-1}. Co więcej ustalony \omega dzieli 2^p. Jednak \omega^{2^{p-1}} \neq 1, więc nie dzieli 2^{p-1}. Przeto, wynosi dokładnie 2^p.

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

2^p \leq |X^*| \leq q^2 - 1 < q^2.

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

q^2 \leq M_p = 2^p-1.

To prowadzi do sprzeczności 2^p < 2^p-1. Dlatego M_p jest pierwsza.

Konieczność[edytuj]

Z drugiej strony, celem jest pokazanie, że pierwszość M_p implikuje s_{p-2} \equiv 0 \pmod{M_p}. Poniższy uproszczony dowód przedstawił Öystein J. R.

Gdy 2^p - 1 \equiv 7 \pmod{12} dla nieparzystych p > 1, z własności symbolu Legendre'a wynika, że (3|M_p) = -1. To oznacza, że 3 jest podwójnym nieresiduum modulo M_p. Dzięki kryterium Eulera, jest to równoważne

3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}.

Natomiast, 2 jest podwójnym residuum modulo M_p ponadto 2^p \equiv 1 \pmod{M_p} i stąd 2 \equiv 2^{p+1} = \left(2^{\frac{p+1}{2}}\right)^2 \pmod{M_p}. Tym razem, kryterium Eulera pozwala napisać

2^{\frac{M_p-1}{2}} \equiv 1 \pmod{M_p}.

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

24^{\frac{M_p-1}{2}} \equiv \left(2^{\frac{M_p-1}{2}}\right)^3 \left(3^{\frac{M_p-1}{2}}\right) \equiv (1)^3(-1) \equiv -1 \pmod{M_p}.

Niech \sigma = 2\sqrt{3}, i zdefiniujmy X tak jak wcześniej jako pierścień X = \{a + b\sqrt{3} \mid a, b \in \mathbb{Z}_{M_p}\}. Wówczas w pierścieniu X, otrzymujemy


\begin{align}
 (6+\sigma)^{M_p}
 &= 6^{M_p} + \left(2^{M_p}\right) \left(\sqrt{3}^{M_p}\right) \\
 &= 6 + 2 \left(3^{\frac{M_p-1}{2}}\right) \sqrt{3} \\
 &= 6 + 2 (-1) \sqrt{3} \\
 &= 6 - \sigma,
\end{align}

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

(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p},

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

a^{M_p} \equiv a \pmod{M_p}

dla każdej liczby całkowitej a. Wartość \sigma została wybrana tak, aby \omega = \frac{(6+\sigma)^2}{24}. Co za tym idzie, może być wykorzystana do wyliczenia \omega^{\frac{M_p+1}{2}} w pierścieniu X jako


\begin{align}
 \omega^{\frac{M_p+1}{2}}
 &= \frac{(6 + \sigma)^{M_p+1}}{24^{\frac{M_p+1}{2}}} \\
 &= \frac{(6 + \sigma) (6 + \sigma)^{M_p}}{24 \cdot 24^{\frac{M_p-1}{2}}} \\
 &= \frac{(6 + \sigma) (6 - \sigma)}{-24} \\
 &= -1.
\end{align}

To co pozostaje to mnożenie obu stron równania przez \bar{\omega}^{\frac{M_p+1}{4}} i wykorzystanie \omega \bar{\omega} = 1, co daje


\begin{align}
 \omega^{\frac{M_p+1}{2}}     \bar{\omega}^{\frac{M_p+1}{4}}   &= -\bar{\omega}^{\frac{M_p+1}{4}} \\
 \omega^{\frac{M_p+1}{4}}   + \bar{\omega}^{\frac{M_p+1}{4}}   &= 0 \\
 \omega^{\frac{2^p-1+1}{4}} + \bar{\omega}^{\frac{2^p-1+1}{4}} &= 0 \\
 \omega^{2^{p-2}}           + \bar{\omega}^{2^{p-2}}           &= 0 \\
 s_{p-2}                                                       &= 0.
\end{align}

Skoro s_{p - 2} jest 0 w X, jest również 0 modulo M_p.

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ą Mersenna Davida Slowinskiego & Paula Gage'a z 4 stycznia, 1994 (znaną 33-cią) z wykładnikiem p=859433 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 M 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, \omega + \langle T^2 - 3 \rangle i \bar{\omega} + \langle T^2 - 3 \rangle należą do X. Poprzez nadużycia językowe \omega and \bar{\omega} są identyfikowane z ich obrazami w X zgodnie z naturalnym naturalnym pierścieniem homomorfizmu z \mathbb{Z}[\sqrt{3}] w X , który przyporządkowuje \sqrt{3} 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]