Rekordowe pierwszaki

Liczby pierwsze (czyli takie, które mają dokładnie dwa dzielniki naturalne) interesowały matematyków od zarania dziejów. Już Euklides w IV w. p.n.e. dowiódł, że jest ich nieskończenie wiele. Dowód przeprowadzony przez Euklidesa jest przykładem tzw. rozumowania „nie wprost". Zakłada się, że liczb pierwszych jest skończenie wiele, i bada, jakie byłyby tego konsekwencje. Oczywiście natychmiast otrzymuje się sprzeczność, bo jeśli {p₁, p₂, p₃, ..., p_n} byłby zbiorem wszystkich liczb pierwszych, to liczba P = p₁p₂p₃ ·...· p_n+1 do tego zbioru nienależąca (bo jest przecież większa od wszystkich jego elementów) również byłaby pierwsza, gdyż nie dzieli się przez żadną liczbę pierwszą (w każdym takim dzieleniu daje resztę 1).

W III w. p.n.e. Eratostenes z Cyreny podał pewien sposób znajdowania liczb pierwszych w skończonych początkowych podzbiorach liczb naturalnych - tzw. sito Eratostenesa. Jest to metoda kolejnego „wysiewania" liczb pierwszych spośród liczb naturalnych większych od 1. Wybieramy najmniejszą liczbę (2) i kolorujemy ją, a potem wykreślamy wszystkie jej wielokrotności (czyli skreślamy mechanicznie co drugą liczbę). Z pozostałych liczb (niepokolorowanych i nieskreślonych) wybieramy pierwszą wolną liczbę (3), kolorujemy, a potem wykreślamy wszystkie jej wielokrotności (niektóre liczby będą w tym procesie skreślane wiele razy). Powtarzamy to postępowanie, aż wszystkie liczby będą skreślone lub pokolorowane. Te kolorowe to będą właśnie liczby pierwsze. 

Od XVII wieku nowych liczb pierwszych szuka się głównie wśród tzw. liczb Mersenne'a, czyli liczb postaci 2^p -1, gdzie p jest pierwsze, choć nie wiadomo, czy jest wśród nich nieskończenie wiele liczb pierwszych ani czy jest wśród nich nieskończenie wiele liczb złożonych. Oczywiście gdy p jest złożone, 2^p-1 pierwsze być nie może, wszak liczba 2^nm-1 dzieli się przez 2ⁿ-1 (dlaczego?). Sam Marin Mersenne [czyt. mar'ę mer'sen] (1588-1648) - francuski mnich franciszkański i matematyk - przypuszczał, że wśród liczb postaci 2^p-1 znajdują się prawie wszystkie liczby pierwsze (tzn. wszystkie poza ew. pewną skończoną liczbą). Matematycy współcześni nadal się nad tym głowią. Mersenne twierdził też (bez dowodu), że liczby 2^p-1 są pierwsze dla p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 i dla żadnych innych liczb naturalnych p<258. Po 300 latach okazało się, że popełnił pięć błędów. Liczby pierwsze otrzymamy także dla p = 61, 89 i 107, a dla p = 67 i 257 otrzymamy liczby złożone. Tym błędom nie należy się dziwić zważywszy na to, że liczby Mersenne’a rosną bardzo szybko, a w tamtych czasach wszystkie obliczenia wykonywano ręcznie. Już wskazanie dzielników liczby 2047 = 2¹¹ – 1 jest dość trudne, a co dopiero liczby 536870911 = 2²⁹ – 1.

Każda liczba złożona musi mieć dzielnik nieprzekraczający pierwiastka kwadratowego z tej liczby (dlaczego?). W oparciu o tę własność można zbadać, czy dana liczba p jest pierwsza - wystarczy sprawdzić, czy nie dzieli się przez żadną z liczb pierwszych mniejszych lub równych √p. Jednak jeśli p jest dużą liczbą, sprawdzenie tego faktu jest bardzo żmudne. Tylko dzięki niezwykłej zręczności rachunkowej matematyk szwajcarski Leonard Euler [czyt. ojler] (1707-1783) udowodnił około 1772 roku, że liczba 2³¹-1 = 2 147 483 647 jest pierwsza. Znajdowanie większych liczb pierwszych bez dodatkowych "sztuczek rachunkowych" byłoby trudne.

Jedną z takich "sztuczek" odkrył francuski matematyk Adrien-Marie Legendre [czyt. adri’ę mar’i le’żądr] (1752-1833). Pokazał, że dzielnikami liczby Mersenne’a z wykładnikiem p mogą być tylko liczby postaci 2kp+1 (k[tex]\in[/tex]N), dające z dzielenia przez 8 resztę 1 lub 7. Na przykład dzielnikami 2¹¹-1 są liczby 23 = 2·11+1 = 7 (mod 8) oraz 89 = 2·4·11+1 = 1 (mod 8). Ograniczyło to znacznie liczbę możliwych dzielników, jakie należy sprawdzać przy badaniu pierwszości liczby Mersenne’a. Ale i tak dla dużych liczb rachunki te pozostały upiorne. A jak Wam poszło szukanie dzielników liczby 2²⁹-1? (O pewnej ciekawostce związanej z osobą Adriena Legendre'a piszemy na Portalu tutaj.)

Przed erą komputerów przez prawie 80 lat największą znaną liczbą pierwszą była odkryta przez kolejnego matematyka francuskiego Françoisa Edouarda Lucasa [nazwisko czytaj frąsu'a edu'ar liu'ka] (1842-1891) w 1876 roku liczba 2¹²⁷-1 = 170 141 183 460 469 231 731 687 303 715 884 105 727 (ma ona 39 cyfr). Jej pierwszości nie dałoby się udowodnić ani sitem Eratostenesa, ani metodą sprawdzania podzielności, ale Lucas odkrył kolejną "sztuczkę". Podany przez niego warunek stwierdzał, że liczba 2^p-1, gdzie p jest pierwsza, sama jest liczbą pierwszą wtedy i tylko wtedy, gdy jest dzielnikiem wyrazu L_p-1 ciągu określonego następująco: L₁=4, L_n=L_n-1² - 2. Nie wiadomo, jak Lucas wymyślił tę własność. Wiemy, że nie potrafił jej formalnie udowodnić.

Warunek podany przez Lucasa został udowodniony dopiero dopiero w XX wieku przez Amerykanina Derricka Henry'ego Lehmera (1905-1991). Ta metoda stosowana jest w dowodzeniu pierwszości liczb Mersenne'a do dziś (choć od tamtej pory wynaleziono jeszcze inne "sztuczki") i nosi nazwę testu Lucasa-Lehmera.  Kolejne wyrazy ciągu L_n to 4, 14, 194, 37634… (nie należy mylić ich z tzw. liczbami Lucasa, powstającymi analogicznie do liczb Fibonacciego, ale z początkowych wyrazów równych 1 i 2). Można sprawdzić, że 2³-1|L₃, 2⁵-1|L₄, ale jak sprawdzić bez kalkulatora, że 2¹²⁷-1|L₁₂₈? A jednak Lucas tego dokonał. Czy potrafisz zrobić to na komputerze?

Jak widać bez komputerów skuteczne poszukiwanie nowych liczb pierwszych byłoby niemożliwe. Następną po liczbie znalezionej przez Lucasa liczbę pierwszą Mersenne'a odkrył Raphael Mitchel Robinson (1911-1995) z Uniwersytetu Kalifornijskiego z Los Angeles dopiero w 1952 roku, używając do tego Standards Western Automatic Computer - prymitywnego komputera lampowego. Liczba odkryta przez Robinsona to 2⁵²¹-1. Ma ona 157 cyfr. Współczesne komputery pierwszość tej liczby sprawdzają w kilkanaście sekund przy użyciu prostych algorytmów.

Rozwój techniki sprawia, że liczba znanych liczb pierwszych szybko rośnie. Na początku XX wieku znane były wszystkie liczby pierwsze poniżej miliona, a na początku XXI wieku - wszystkie poniżej 2 miliardów. Jest ich ponad 98 milionów, chociaż w ogóle znanych jest dużo więcej liczb pierwszych (np. te znalezione przez Lucasa i Robinsona) tylko niekolejnych. Jednak nadal nie znamy efektywnego wzoru na wyznaczenie nieskończenie wielu takich liczb (o wzorze opisującym wszystkie liczby pierwsze, choć nie nadającym się do ich obliczania możesz przeczytać w artykule Czy istnieje wzór na n-tą liczbę pierwszą?).

Poszukiwanie dużych liczb pierwszych jest bardzo ważnym problemem. Mają one zastosowanie we współczesnej kryptografii, czyli teorii kodowania informacji, choć największe znane dziś liczby pierwsze są zbyt duże, aby mieć jakieś znaczenie praktyczne. Jest to jednak znakomita reklama dla firm komputerowych i programistów, gdyż do zbadania pierwszości liczby nie wystarczy zapuścić jakiegoś prostego algorytmu i wystarczająco długo czekać. Komputery wykonują przecież działania na liczbach o ograniczonej liczbie cyfr, a współcześnie w grę wchodzą liczby o milionach cyfr. Jednak sam proces poszukiwania dużych liczb pierwszych ma ważne zastosowania. Jego oprogramowanie jest używane jako narzędzie testujące urządzenia komputerowe, np. na początku 2016 roku odkryto w ten sposób usterkę w najnowszym CPU (central processing unit) firmy Intel.

Poszukiwanie ogromnych liczb pierwszych już dawno przekroczyło możliwości obliczeniowe pojedynczego komputera. Dlatego od wielu lat prowadzi się zbiorowe poszukiwania nowych liczb pierwszych w ramach tzw. obliczeń rozproszonych. Najbardziej znanym międzynarodowym projektem w tym zakresie jest uruchomiony w 1996 roku przez matematyka Georgea Woltmana (ur. 1957) - absolwenta MIT (Massachusetts Institute of Technology w Cambridge, USA) - projekt GIMPS (Great Internet Mersenne Prime Search). W czasie 20 lat jego trwania (do 2016 roku) odkryto dzięki niemu 15 rekordowo dużych na dany moment liczb pierwszych Mersenne'a. Do tych poszukiwań może dołączyć każdy posiadacz komputera. Wystarczy przeczytać więcej o projekcie GIMPS na stronie http://www.mersenne.org i pobrać z niej odpowiednie oprogramowanie, które działa automatycznie w wolnym czasie komputera. Przy odrobinie szczęścia może się to okazać niezwykle dochodowe.

Aby zachęcić społeczność internautów do udziału we wspólnych poszukiwaniach, Electronic Frontier Foundation ufundowała nagrody w wysokości 50 000 dolarów za odkrycie pierwszej liczby pierwszej o więcej niż milionie cyfr (wypłacono ją w 2000 roku) oraz 100 000 dolarów dla odkrywcy pierwszej w historii liczby pierwszej o więcej niż 10 milionach cyfr. Ta pula została rozbita 23 sierpnia 2008 roku. Tego dnia na Uniwersytecie Kalifornijskim w Los Angeles (tam gdzie pracował niegdyś Robinson) komputer pracujący w sieci GIMPS PrimeNet odkrył 45. znaną pierwszą liczbę Mersenne'a, która wynosi 2^{43 112 609}-1  i ma 12 978 189 cyfr. Gratulacje należą się Edsonowi Smithowi - pracownikowi biblioteki odpowiedzialnemu za zainstalowanie i utrzymanie oprogramowania GIMPS.
Pechowo, bo zaledwie 2 tygodnie później 6 września 2008 roku niemiecki inżynier, pasjonat projektu GIMPS - Hans Michael Elvenich z Langenfeld koło Kolonii odkrył 46. znaną pierwszą liczbę Mersenne'a wynoszącą 2^{37 156 667}-1 (ma 11 185 272 cyfr, więc jest mniejsza niż amerykańska rekordzistka, ale również spełnia warunki nagrody). Był to pierwszy przypadek od 1988 roku, gdy liczby Mersenne'a nie były odkryte w kolejności rosnącej wielkości. Ostatecznie administratorzy projektu GIMPS, którym przypadła nagroda Electronic Frontier Foundation wypłacili 50 000 dolarów Wydziałowi Matematyki na Uniwersytecie Kalifornijskim, 25 000 podzielili między odkrywców poprzednich 6 liczb Mersenne'a, a 25 000 przekazali na cele charytatywne. Kolejne nagrody wyznaczone przez EFF wynoszą: 150 000 dolarów za przekroczenie 100 mln cyfr oraz 250 000 dolarów za przekroczenie miliarda cyfr. Więcej o tej fundacji można przeczytać na stronie http://www.eff.org. Obecnie projekt GIMPS zbiera fundusze i wypłaca nagrody pieniężne (ale nie tak wysokie jak EFF) za każdą znalezioną nową liczbę pierwszą Mersenne'a.

Pierwszość każdej liczby znalezionej w projekcie GIMPS weryfikuje się potem kilkukrotnie za pomocą niezależnego oprogramowania (co zajmuje zazwyczaj ok. miesiąca) i dopiero ogłasza publicznie. Za datę odkrycia nowej rekordowo dużej liczby pierwszej uznaje się jednak tradycyjnie moment jej pierwszego zauważenia przez człowieka (a nie wykrycia przez komputer). Z tego powodu znaleziona w 1961 roku 19. liczba pierwsza Mersenne'a wynosząca 2⁴²⁵³-1 nigdy nie była uznana za rekordową znaną liczbę pierwszą, bowiem amerykański matematyk Alexander Hurwitz (ur. 1937), przeglądając raport komputerowy od tyłu, jako pierwszą zauważył na wydruku liczbę 2⁴⁴²³-1 (20. liczbę pierwszą Mersenne'a), a dopiero później znalezioną wcześniej przez komputer liczbę 2⁴²⁵³-1.

Warto zauważyć, że liczby pierwsze Mersenne'a mają podwójną numerację i nazewnictwo, ze względu na chronologię ich odkrywania i kolejność występowania w liczbach naturalnych). Kiedy w 2006 roku potwierdzono pierwszość liczby 2^{32 582 657}-1 (jej zapis dziesiętny ma 9 808 358 cyfr), była to 44. znana liczba pierwsza Mersenne'a, ale nie wiadomo było, czy znane są wszystkie pierwsze liczby Mersenne'a od niej mniejsze. Przez kolejnych 8 lat w ramach projektu GIMPS zbadano liczby Mersenne'a dla mniejszych wykładników i w listopadzie 2014 ogłoszono, że 44. znana liczba pierwsza Mersenne'a jest w istocie 44. liczbą pierwszą Mersenne'a. O dalszych znanych dziś liczbach pierwszych Mersenne'a nie wiadomo na razie, którymi są kolejnymi liczbami pierwszymi Mersenne'a. 

W kwietniu 2009 znaleziono (a w czerwcu zweryfikowano) 47. znaną liczbę pierwszą Mersenne'a.
Jest nią 2^42643801-1. Liczba ta ma 12 837 064 cyfr i została znaleziona przez Odda Magnara Strindmo z Melhus w Norwegii (w ramach projektu GIMPS). Jest to druga co do wielkości znana w tej chwili liczba pierwsza (jest większa niż 46. i mniejsza niż 45. znana liczba Mersenne'a) i jest 13. znalezioną w ramach projektu GIMPS w jego 13-letniej historii. 

W styczniu 2013 znaleziono i zweryfikowano 48. znaną liczbę pierwszą Mersenne'a.

Jest nią 2^{57 885 161}-1. Liczba ta ma 17 425 170 cyfr i została znaleziona przez Curtisa Coopera z University of Central Misouri w USA. To już trzecie odkrycie rekordowej liczby pierwszej na komputerach tego uniwersytetu (poprzednie rekordy padły w latach 2005 i 2006). Stwierdzenie pierwszości tej liczby zabrało 39 dni nieprzerwanej pracy procesora. Nagroda wypłacona za to odkrycie wyniosła 3000 dolarów.

W styczniu 2016 znaleziono i zweryfikowano 49. znaną liczbę pierwszą Mersenne'a.

Jest nią 2^74207281-1. Liczba ta ma 22 338 618 cyfr (prawie 5 milionów więcej niż poprzednia). Komputery dokonały tego już we wrześniu 2015, ale nie zostało to od razu zauważone (automatyczny e-mail powiadamiający o dokonaniu odkrycia nie dotarł na konto adresata). Szczęśliwcem po raz czwarty został dr Curtis Cooper z University of Central Misouri w USA (poprzednio znalazł 43. 44. i 48. znaną liczbę pierwszą Mersennea). To piętnasta liczba odkryta w projekcie GIMPS, która uświetnia jubileusz 20-lecia jego działalności. Za swoje odkrycie Cooper zainkasował kolejne 3000 dolarów. Rekordowa liczba została tym razem wydrukowana na papierze. Można ją zobaczyć w kanale Numberphile, w filmiku Matta Parkera (Queen Mary University of London) - tutaj.

W grudniu 2017 znaleziono i zweryfikowano 50. znaną liczbę pierwszą Mersenne'a.

Jest nią 2^77232917–1. Liczba ta ma 23 249 425 cyfr. Odkrycia dokonano w drugi dzień świąt Bożego Narodzenia na komputerze jednego z uczestników projektu GIMPS - Jonathana Pace'a - 51-letniego amerykańskiego inżyniera elektryka z Germantown w stanie Tennessee. W projekcie uczestniczył od 14 lat. Otrzymał nagrodę 3000 dolarów. Weryfikacja poprawności wyniku za pomocą czterech różnych systemów komputerowych i z użyciem innego w każdym przypadku oprogramowania zajęła 6 dni.

W grudniu 2018 znaleziono i zweryfikowano 51. znaną liczbę pierwszą Mersenne'a.

Jest nią 2^82.589.933–1. Liczba ta ma 24.862.048 cyfr (to ponad 1,5 mln cyfr więcej niż poprzednia rekordzistka sprzed roku). Odkrycia dokonano 7 XII na komputerze jednego z uczestników projektu GIMPS - Patricka Laroche'a z Ocali w stanie Floryda. Miał sporo szczęścia, gdyż wynik ten pojawił się już po 4 miesiącach jego uczestnictwa w projekcie.

 Na koniec pytanie dla Czytelników: ile trwałoby zapisanie aktualnie rekordowej liczby pierwszej na papierze i ile papieru byłoby na to potrzebne?