Największa odkryta znana liczba pierwsza: Dlaczego to ma znaczenie

W filmie Kontakt, opartym na powieści Carla Sagana o tym samym tytule, dr Ellie Arroway szuka inteligentnego życia pozaziemskiego, skanując niebo za pomocą teleskopy radiowe. Kiedy Arroway, grana przez Jodie Foster, rozpoznaje liczby pierwsze w sygnale międzyplanetarnym, uważa, że to dowód na to, że obca inteligencja wysłała wiadomość do rasy ludzkiej.

Liczba jest uważana za liczbę pierwszą, jeśli jest podzielna tylko przez jeden i siebie. Na przykład dwa, trzy, pięć i siedem są liczbą pierwszą. Liczba 15, która jest trzy razy pięć, nie jest liczbą pierwszą. To nie przypadek, że Arroway uważa, że kosmici w Kontaktu używają liczb pierwszych jako kosmicznego „cześć” – są one elementami składowymi innych liczb. Każda liczba jest iloczynem liczb pierwszych.

W grudniu 2017 roku największa znana Liczbę pierwszą odkryto za pomocą wyszukiwania komputerowego. Liczbę pierwszą odkrył Jonathan Pace, inżynier elektryk, który obecnie pracuje w FedEx. Dlaczego jest to ważne? Ponieważ bez liczb pierwszych Twoje dane bankowe, transakcje Paypal lub zakupy Amazon mogą zostać naruszone.

Duże liczby pierwsze, takie jak ta właśnie odkryta, odgrywają kluczową rolę w cyberbezpieczeństwie. Kryptografia to nauka o kodowaniu i dekodowaniu informacji, a wiele jej algorytmów, takich jak RSA, opiera się w dużym stopniu na liczbach pierwszych.

Liczby pierwsze Mersennea

Chociaż istnieje nieskończenie wiele liczb pierwszych, nie jest znane f ormula, aby je wszystkie wygenerować. Trwa wyścig w celu znalezienia większych liczb pierwszych za pomocą kombinacji technik matematycznych i obliczeń.

Jednym ze sposobów uzyskania dużych liczb pierwszych jest koncepcja matematyczna odkryta przez XVII-wiecznego francuskiego mnicha i uczonego, Marina Mersennea.

Liczba pierwsza Mersennea ma postać 2ⁿ – 1, gdzie n jest dodatnią liczbą całkowitą. Pierwsze cztery z nich to trzy, siedem, 31 i 127.

Jednak nie każda liczba w postaci 2ⁿ – 1 jest liczbą pierwszą; na przykład 2⁴ – 1 = 15. Jeśli 2ⁿ – 1 jest liczbą pierwszą, można wykazać, że samo n musi być liczbą pierwszą. Ale nawet jeśli n jest liczbą pierwszą, nie ma gwarancji, że liczba 2ⁿ – 1 jest liczbą pierwszą: 2¹¹ – 1 = 2,047, co nie jest liczbą pierwszą, ponieważ wynosi 23 razy 89.

Znanych jest tylko 50 liczb pierwszych Mersennea . Nierozwiązanym przypuszczeniem jest to, że istnieje ich nieskończona liczba.

Poszukiwanie nowych liczb pierwszych

Great Internet Mersenne Prime Search (lub GIMPS) to wspólny wysiłek wielu osób i zespoły z całego świata, aby znaleźć nowe liczby pierwsze Mersenne. George Woltman rozpoczął GIMPS w 1996 r., Aw 2018 r. Obejmuje on ponad 183 000 ochotników, którzy wspólnie zasilają ponad 1,6 miliona procesorów.

Ostatnio odkryta liczba pierwsza Mersenne jest zwięźle zapisana jako 2⁷⁷²³²⁹¹⁷ – 1; to jest dwa pomnożone przez siebie 77,232,917 razy, minus jeden. Odkrycie Jonathana Pacea wymagało sześciu dni obliczeń na czterordzeniowym procesorze Intel i5-6600 i zostało niezależnie zweryfikowane przez cztery inne grupy.

Nowo odkryta liczba pierwsza ma aż 23 249 425 cyfr. Aby zrozumieć, jak duże to jest, załóżmy, że wypełniliśmy książkę cyframi, z których każda liczy się jako słowo, a każda książka ma 100 000 słów. Wtedy cyfry 2⁷⁷²³²⁹¹⁷ – 1 zapełniłyby około 232 książek!

W jaki sposób GIMPS znajduje liczby pierwsze?

GIMPS używa testu Lucasa-Lehmera dla liczb pierwszych. W tym celu utwórz sekwencję liczb całkowitych zaczynających się od czterech, których wyrazy są poprzednimi członami podniesionymi do kwadratu i minus dwa. Test mówi, że liczba 2ⁿ – 1 jest liczbą pierwszą, jeśli dzieli (n-2) -ty człon w ciągu.

Podczas gdy test Lucasa-Lehmera wydaje się dość łatwy do sprawdzenia, obliczeniowe wąskie gardło w stosowaniu pochodzi z kwadratów liczb. Mnożenie liczb całkowitych to coś, co każdy dzieciak w wieku szkolnym może zrobić, ale przy dużych liczbach stwarza problemy, nawet dla komputerów. Jednym ze sposobów obejścia tego jest użycie szybkich transformacji Fouriera (FFT), algorytmów przyspieszających obliczenia.

Każdy może zaangażować się w GIMPS – o ile masz przyzwoity komputer z połączeniem internetowym. Darmowe oprogramowanie do wyszukiwania liczb pierwszych Mersennea można znaleźć na stronie GIMPS.

Chociaż największa znana liczba pierwsza jest oszałamiająco masywna, poza nią czeka na odkrycie nieskończenie wiele więcej liczb pierwszych. Tak jak Ellie Arroway w Contact, musimy tylko ich szukać.