Test Lucasa-Lehmera

Test Lucasa-Lehmera – test 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 ${\displaystyle M_{p}}$ oznacza liczbę Mersenne’a ${\displaystyle M_{p}=2^{p}-1}$ dla pewnej nieparzystej liczby pierwszej ${\displaystyle p}$ (tzn. liczby pierwszej większej od 2). Pierwszość liczby ${\displaystyle p}$ można sprawdzić za pomocą prostego algorytmu podziału, gdzie ${\displaystyle p}$ jest wykładniczo mniejsza od ${\displaystyle M_{p}.}$ Definiuje się następujący ciąg liczb naturalnych ${\displaystyle (S_{k}){:}}$

${\displaystyle S_{k}={\begin{cases}4&{\mbox{gdy }}k=0,\\S_{k-1}^{2}-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^[1]).

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

${\displaystyle S_{p-2}\equiv 0{\pmod {M_{p}}}.}$

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

liczba Mersenna ${\displaystyle M_{p}}$ jest pierwsza wtedy i tylko wtedy, gdy residuum Lucasa-Lehmera liczby ${\displaystyle 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)
    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 ${\displaystyle p}$-bitowe (w innym przypadku liczba bitów byłaby dublowana w każdej iteracji).

Złożoność czasowa

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

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

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

${\displaystyle {\begin{aligned}916{\bmod {2}}^{5}-1&=1110010100_{2}{\bmod {2}}^{5}-1\\&=11100_{2}+10100_{2}{\bmod {2}}^{5}-1\\&=110000_{2}{\bmod {2}}^{5}-1\\&=1_{2}+10000_{2}{\bmod {2}}^{5}-1\\&=10001_{2}{\bmod {2}}^{5}-1\\&=10001_{2}\\&=17.\end{aligned}}}$

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

Przykłady

Liczba Mersenne’a M₃ = 7 jest pierwsza. Test Lucasa-Lehmera sprawdza to w następujący sposób. Początkowo ${\displaystyle 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ść ${\displaystyle s}$ wynosi 0, wnioskujemy, że M₃ jest pierwsza.

Z drugiej strony, M₁₁ = 2047 = 23 × 89 nie jest pierwsza. Powtórnie, ${\displaystyle 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ść ${\displaystyle s}$ nie jest równa  0, wnioskujemy, że M₁₁ = 2047 nie jest pierwsza. Mimo że M₁₁ = 2047 posiada nietrywialne czynniki, test Lucasa-Lehmera nie daje żadnych wskazówek, jakie mogą one być.

Dowód

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

${\displaystyle 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 ${\displaystyle M_{p}}$ jest pierwsza wtedy i tylko wtedy, gdy ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}$

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

${\displaystyle s_{0}=\omega ^{2^{0}}+{\overline {\omega }}^{2^{0}}=\left(2+{\sqrt {3}}\right)+\left(2-{\sqrt {3}}\right)=4}$

i

${\displaystyle {\begin{aligned}s_{n}&=s_{n-1}^{2}-2\\&=\left(\omega ^{2^{n-1}}+{\overline {\omega }}^{2^{n-1}}\right)^{2}-2\\&=\omega ^{2^{n}}+{\overline {\omega }}^{2^{n}}+2(\omega {\overline {\omega }})^{2^{n-1}}-2\\&=\omega ^{2^{n}}+{\overline {\omega }}^{2^{n}}.\end{aligned}}}$

Ostatni krok wykorzystuje ${\displaystyle \omega {\overline {\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ść

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

${\displaystyle \omega ^{2^{p-2}}+{\overline {\omega }}^{2^{p-2}}=kM_{p}}$

dla pewnego całkowitego ${\displaystyle k,}$ więc

${\displaystyle \omega ^{2^{p-2}}=kM_{p}-{\overline {\omega }}^{2^{p-2}}.}$

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

${\displaystyle \left(\omega ^{2^{p-2}}\right)^{2}=kM_{p}\omega ^{2^{p-2}}-(\omega {\overline {\omega }})^{2^{p-2}}.}$

Zatem

${\displaystyle \omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad (1)}$

Dla uzyskania sprzeczności, przypuśćmy, że ${\displaystyle M_{p}}$ jest złożona, i niech ${\displaystyle q}$ będzie najmniejszym pierwszym czynnikiem liczby ${\displaystyle M_{p}.}$ Liczby Mersenne’a są nieparzyste, więc ${\displaystyle q>2.}$ Niech ${\displaystyle \mathbb {Z} _{q}}$ będzie zbiorem liczb całkowitych modulo ${\displaystyle q}$ i niech ${\displaystyle X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.}$ Mnożenie w ${\displaystyle X}$ jest zdefiniowane, jak następuje

${\displaystyle \left(a+{\sqrt {3}}b\right)\left(c+{\sqrt {3}}d\right)=[(ac+3bd)\,{\bmod {\,}}q]+{\sqrt {3}}[(ad+bc)\,{\bmod {\,}}q].}$

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

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

Teraz ${\displaystyle M_{p}\equiv 0{\pmod {q}}}$ i ${\displaystyle \omega \in X,}$ więc

${\displaystyle kM_{p}\omega ^{2^{p-2}}=0}$

w ${\displaystyle X.}$

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

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

w ${\displaystyle X}$ i podnosząc obie strony do kwadratu, otrzymujemy

${\displaystyle \omega ^{2^{p}}=1.}$

Zatem ${\displaystyle \omega }$ należy do ${\displaystyle X^{*}}$ i posiada odwrotność ${\displaystyle \omega ^{2^{p}-1}.}$ Co więcej, rząd ${\displaystyle \omega }$ dzieli ${\displaystyle 2^{p}}$, jednak ${\displaystyle \omega ^{2^{p-1}}\neq 1,}$ więc nie dzieli on ${\displaystyle 2^{p-1}}$. Wobec tego rząd ${\displaystyle \omega }$ wynosi dokładnie ${\displaystyle 2^{p}.}$

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

${\displaystyle 2^{p}\leqslant |X^{*}|\leqslant q^{2}-1<q^{2}.}$

Ale ${\displaystyle q}$ jest najmniejszym pierwszym czynnikiem rozkładu liczby złożonej ${\displaystyle M_{p},}$ więc

${\displaystyle q^{2}\leqslant M_{p}=2^{p}-1.}$

To prowadzi do sprzeczności ${\displaystyle 2^{p}<2^{p}-1.}$ Dlatego ${\displaystyle M_{p}}$ jest pierwsza.

Konieczność

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

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

${\displaystyle 3^{\frac {M_{p}-1}{2}}\equiv -1{\pmod {M_{p}}}.}$

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

${\displaystyle 2^{\frac {M_{p}-1}{2}}\equiv 1{\pmod {M_{p}}}.}$

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

${\displaystyle 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 ${\displaystyle \sigma =2{\sqrt {3}}}$ i zdefiniujmy ${\displaystyle X}$ tak jak wcześniej jako pierścień ${\displaystyle X=\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{M_{p}}\}.}$ Wówczas w pierścieniu ${\displaystyle X}$ otrzymujemy

${\displaystyle {\begin{aligned}(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{aligned}}}$

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

${\displaystyle (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

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

To co pozostaje, to mnożenie obu stron równania przez ${\displaystyle {\overline {\omega }}^{\frac {M_{p}+1}{4}}}$ i wykorzystanie ${\displaystyle \omega {\overline {\omega }}=1,}$ co daje

${\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}{\overline {\omega }}^{\frac {M_{p}+1}{4}}&=-{\overline {\omega }}^{\frac {M_{p}+1}{4}}\\\omega ^{\frac {M_{p}+1}{4}}+{\overline {\omega }}^{\frac {M_{p}+1}{4}}&=0\\\omega ^{\frac {2^{p}-1+1}{4}}+{\overline {\omega }}^{\frac {2^{p}-1+1}{4}}&=0\\\omega ^{2^{p-2}}+{\overline {\omega }}^{2^{p-2}}&=0\\s_{p-2}&=0.\end{aligned}}}$

Skoro ${\displaystyle s_{p-2}}$ jest 0 w ${\displaystyle X,}$ jest również 0 modulo ${\displaystyle M_{p}.}$

Zastosowanie

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

Kod w Mathematica

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 ${\displaystyle p=859433}$) 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 ${\displaystyle M}$ 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

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ż

• Édouard Lucas
• Derrick Henry Lehmer
• GIMPS

Uwagi

Przypisy

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Lucas-Lehmer test, [w:] MathWorld, Wolfram Research  (ang.).
• GIMPS. The Great Internet Mersenne Prime Search. (ang.).
• Tony Reix: A LLT-like test for proving the primality of Fermat numbers. Cornell University, 2007-05-24. (ang.).
• Lucas-Lehmer test. MersenneWiki. [zarchiwizowane z tego adresu (2018-04-15)]. (ang.).