Rekordowe liczby pierwsze | Politechnika Gdańska

Już Euklides udowodnił, że liczb pierwszych jest nieskończenie wiele. Rzeczywiście, załóżmy, że mamy pełną listę wszystkich liczb pierwszych 2, 3, …, p_max. Rozważmy liczbę całkowitą N = (2 ∙ 3 ∙…∙ p_max)+1. Kiedy dzielimy N przez 2 dostajemy resztę 1. Tak samo jest, gdy dzielimy ją przez każdą z liczb pierwszych na liście. N jest liczbą pierwszą lub złożoną. W pierwszym przypadku jest większa od p_max. W drugim może być rozdzielona na liczby pierwsze. Ale wówczas żadnym z jej czynników nie może być 2, 3, …, p_max. Zatem istnieje liczba pierwsza większa od p_max. Dzisiaj poszukiwanie kolejnych rekordowych liczb pierwszych jest miarą zdolności obliczeniowych współczesnych superkomputerów i sieci komputerowych.
Jednym z bodźców do poszukiwania nowych liczb pierwszych było po prostu współzawodnictwo. W latach 70. ubiegłego stulecia uczelnie były tak dumne z odkrycia kolejnej rekordowej liczby pierwszej, że rozpowszechniały takie wiadomości na kopertach listów. Np. Uniwersytet Illinois używał takiego datownika do roku 1976, tj. do chwili, gdy na tym uniwersytecie udowodniono słynne twierdzenie o 4 barwach (patrz Grafo-mania, czyli rzecz o grafach i algorytmach. Twierdzenie o czterech barwach, „Pismo PG” nr 5/2021, s. 46–47).
W historii odkrywania coraz większych liczb pierwszych można wyróżnić 3 okresy:

• etap samotnych badaczy, do roku 1951; przy czym od starożytności do wieku XX posługiwano się metodą zwykłego dzielenia liczb;
• etap obliczeń komputerowych, 1952–1996; byli to samotni badacze lub zespoły programistów;
• etap obliczeń rozproszonych, który trwa od 1996 roku do dziś. Chodzi tutaj głównie o projekt Great Internet Mersenne Prime Search (GIMPS).

Historia odkrywania coraz większych liczb pierwszych jest bardzo pouczająca. W XVII wieku mnich francuski Marin Mersenne napisał: „żeby rozstrzygnąć, czy dana liczba piętnasto- lub dwudziestocyfrowa jest pierwszą czy nie, wieki nie wystarczą, czegokolwiek by nie użyć”. Dziś wiemy, jak bardzo się mylił. O tym, jak trudne jest to zadanie, świadczy fakt, że z chwilą zaangażowania komputerów do tego przedsięwzięcia zauważono, że komputerowe znalezienie kolejnej liczby pierwszej Mersenne’a wymagało czterokrotnie więcej czasu niż ponowne odkrycie (i sprawdzenie) poprzedzających tę liczbę liczb pierwszych.

Największe liczby pierwsze

W roku 1644 Mersenne napisał, że liczby postaci 2ⁿ – 1 są pierwsze dla n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257. Dopiero później wykazano, że mylił się dla 67 i 257. Na jego cześć liczby tej postaci nazywamy liczbami Mersenne’a. Spostrzeżenia Mersenne’a nie da się uratować, zakładając, że n też musi być nieparzyste, gdyż 2¹¹ – 1 = 23 ∙ 89. Przez następne dwa stulecia nikt nie był w stanie tego potwierdzić ani zaprzeczyć. Dopiero w roku 1876 Edouardowi Lucasowi udało się udowodnić, że 2¹²⁷ – 1 jest liczbą pierwszą i do roku 1952 była to największa znana liczba pierwsza. Obecnie największą znaną liczbą pierwszą jest 51. liczba pierwsza Mersenne’a: 2^82589933 – 1 odkryta 7 grudnia 2018 roku. Do jej zapisu dziesiętnego trzeba użyć 24 862 048 cyfr. Samo potwierdzenie, że liczba ta jest
w istocie pierwszą, było sprawą niebanalną i wymagało 12 dni nieprzerwanego przetwarzania na komputerze z procesorem Intel i5-4590T.
Aktualnie osiem największych znanych liczb pierwszych są to liczby pierwsze Mersenne’a. Największą znaną liczbą pierwszą, która nie jest liczbą Mersenne’a, jest: 10 223 ∙ 2^31172165 + 1, która została odkryta w roku 2016, a jej zapis dziesiętny liczy ponad 9 milionów cyfr. Warto dodać, że fundacja Electronic Frontier Foundation (EFF) wyznaczyła nagrodę 150 tys. dolarów za zidentyfikowanie liczby pierwszej mającej ponad 100 milionów cyfr w zapisie dziesiętnym.
Natomiast największą liczbą pierwszą poznaną przed erą elektroniki jest liczba znaleziona w 1951 roku przez Francuza Aimé Ferriera (tab. 1). Napisaliśmy, że liczba ta została poznana przed erą komputerową, ponieważ jej odkrywca nie używał komputera do obliczeń. Zawiera ona „jedynie” 44 cyfry. W tabeli 3 podajemy 17 największych liczb pierwszych o postaci mersennowskiej. Osiem z nich to największe liczby pierwsze w konkurencji z liczbami niemersennowskimi.
Obecnie świat oczekuje na znalezienie 52. liczby pierwszej Mersenne’a, ponieważ poprzednia została odkryta przed prawie pięcioma laty. Nie wydaje się, by ta liczba sięgnęła po nagrodę ufundowaną przez EFF.

Marek Kubale  kubale@eti.pg.edu.pl