Liczby pierwsze idą w miliony. I to fajna zabawa
Jesienią ubiegłego roku pojawiła się informacja o dokonanym przez Luke’a Duranta – informatyka z San Jose w Kalifornii – odkryciu, które zdetronizowało poprzednią najdłuższą znaną od sześciu lat liczbę pierwszą, co było wyjątkowo długim okresem panowania. Można to jednak uzasadnić tym, że im liczby pierwsze są większe, tym rzadziej są rozmieszczone, a tym samym coraz trudniej trafić na każdą następną.
Nowe odkrycie oszałamia ciągiem 41 024 320 cyfr. Dla porównania – szacuje się, że liczba atomów w obserwowalnym Wszechświecie ma 80 cyfr. Każda kolejna cyfra oznacza 10-krotny wzrost, zatem wielkość nowej liczby pierwszej przekracza ludzką wyobraźnię.
Liczby pierwsze pełnią ważną funkcję w tzw. czystej matematyce – pierwszoplanową w dziedzinie zwanej teorią liczb. Natomiast w praktyce stanowią podstawę algorytmów szyfrowania. Liczba pierwsza złożona z ponad 41 mln cyfr nie dołącza bezpośrednio do liczb użytecznych, ale dodaje splendoru społeczności, która pragnie zrozumieć zasady rządzące światem wielkich liczb.
Sukces Duranta był możliwy dzięki nowemu, pomysłowemu oprogramowaniu dostępnemu w ramach projektu Great Internet Mersenne Prime Search (GIMPS) oraz zgromadzonemu sprzętowi o wielkiej mocy obliczeniowej. Powstał obejmujący 17 krajów „superkomputer w chmurze”, kończąc tym samym długą tradycję odkrywania liczb pierwszych przez komputery osobiste.
Liczby pierwsze są często nazywane cegiełkami matematyki, ponieważ każda liczba całkowita większa od 1 jest albo liczbą pierwszą, albo iloczynem unikalnego zbioru liczb pierwszych. Na przykład 15 jest iloczynem liczb pierwszych 5 i 3, natomiast 13 nie można rozłożyć w ten sposób, więc jest to liczba pierwsza. Badanie tych liczb zapoczątkowali starożytni Grecy. W 300 roku p.n.e. Euklides w traktacie Elementy udowodnił, że liczb pierwszych jest nieskończenie wiele. Odtąd niektórzy matematycy i miłośnicy matematyki chętnie zajmują się ich poszukiwaniem. Początek ich ciągu jest w stanie podać każdy (2, 3, 5, 7, 11, …), ale dalej zadanie staje się coraz trudniejsze. Przez tysiąclecia odkrywanie liczb pierwszych było efektem ręcznych obliczeń. Dopiero w roku 1951 do poszukiwań włączyły się komputery. Jednak nawet łowcy nagród z Doliny Krzemowej mają problem z wykrywaniem liczb pierwszych w bardzo odległych zakresach osi liczbowej, ponieważ testowanie pierwszości wielkich liczb nie jest trywialne. Badacze radzą sobie z tym, stosując różne sztuczki optymalizacyjne, by przyspieszyć testy lub zawęzić obszar poszukiwań, co zwiększa szanse odkrycia nowej liczby pierwszej.
Zastanówmy się, jak ustalić, czy 99 400 891 jest liczbą pierwszą? Moglibyśmy po prostu dzielić ją kolejno przez każdą mniejszą liczbę, aby znaleźć jej dzielniki. Ale to prawie sto milionów sprawdzeń względnie małej 8-cyfrowej liczby. Do ograniczenia pracy prowadzi uświadomienie sobie, że nie trzeba dzielić przez każdą mniejszą liczbę, lecz tylko przez liczby pierwsze. A to dlatego, że szukamy tylko jednego dzielnika podanej liczby.
Jeśli np. liczba jest podzielna przez 15, to dzieli się także przez jej czynniki pierwsze, czyli 3 i 5, więc wystarczy sprawdzić tylko te dwie liczby, aby stwierdzić możliwą pierwszość lub jej brak. Poza tym nie trzeba sprawdzać każdej mniejszej liczby pierwszej, lecz tylko w zakresie do pierwiastka kwadratowego z 99 400 891, czyli do liczby, która pomnożona przez samą siebie daje ten ośmiocyfrowy wynik. Jeśli żadna z liczb pierwszych z tego zakresu nie dzieli 99 400 891, można przestać szukać, bo iloczyn dwóch liczb większych niż pierwiastek kwadratowy z 99 400 891 tę liczbę przekroczy. Takie „sztuczki” radykalnie wyszukiwanie skracają – z prawie 100 mln działań do zaledwie 1228 (tyle jest liczb pierwszych mniejszych od pierwiastka kwadratowego z 99 400 891). Ostatecznie: 99 400 891 = 9967×9973, więc nie jest to liczba pierwsza.
Takie ograniczanie działań może być efektywne w przypadku 8-cyfrowej liczby, ale jak Durant poradził sobie z mającą 41 024 320 cyfr? Szukanie wśród gigantów jest prostsze dzięki skoncentrowaniu się na liczbach pierwszych określonego rodzaju. Chodzi o liczby Mersenne’a, nazwane tak na cześć francuskiego teologa Marina Mersenne’a, który badał je w XVII wieku. Liczby te powstają jako iloczyn pewnej liczby dwójek pomniejszony o 1, czyli zgodnie z równaniem 2n–1. Mersenne zauważył, że dla niektórych wartości n wyniki są liczbami pierwszymi. Konkretnie: różnica 2n–1 może być liczbą pierwszą tylko wtedy, gdy n jest liczbą pierwszą, ale nie zawsze tak musi być.
Liczby Mersenne’a są wyjątkowe dla łowcy liczb pierwszych, bo znamy szybką metodę sprawdzenia, czy liczba postaci 2n–1 jest pierwsza. Metoda nazywa się testem pierwszości Lucasa-Lehmera (nazwa pochodzi od nazwisk matematyków – francuskiego, Édouarda Lucasa, który test odkrył, i amerykańskiego, Derricka Henry’ego Lehmera, który twierdzenie udowodnił i test udoskonalił). Jest on znacznie szybszy niż każda inna metoda dla liczb innej postaci.
Test Lucasa-Lehmera stanowi podstawę projektu GIMPS, uruchomionego w 1996 roku i umożliwiającego każdemu wolontariuszowi pobranie bezpłatnego kodu źródłowego. Po uruchomieniu kodu na swoim komputerze można wyszukiwać liczby pierwsze Mersenne’a. Podejście crowdsourcingowe i ograniczenie do liczb pierwszych Mersenne’a okazały się skuteczne. Siedem największych znanych liczb pierwszych to liczby Mersenne’a – wszystkie zostały znalezione w ramach projektu GIMPS. Wypada zauważyć, że mniejsze nieznane liczby pierwsze z pewnością istnieją, ale ponieważ nie znamy wystarczająco skutecznych metod ich sprawdzania, na razie pozostają w ukryciu.
Ogółem wolontariusze znaleźli 18 nowych liczb pierwszych Mersenne’a, z których 17 odkryto dzięki komputerom osobistym hobbystów. Durant, 36-letni były pracownik Nvidii, przerwał tę passę. Nvidia, która ostatnio na krótko wyprzedziła Apple jako najwyżej wyceniana firma na świecie, projektuje specjalistyczne układy komputerowe – procesory graficzne (GPU). Procesory te zostały wprowadzone w celu szybszego renderowania grafiki, ale świetnie sprawdzają się również w innych zadaniach, wymagających obliczeń o wysokim stopniu równoległości – gdy wiele procesorów działa jednocześnie w celu rozwiązania problemu. Takim problemem może być uczenie sieci neuronowych, na przykład dużego modelu językowego GPT-4, wydobywanie kryptowaluty oraz – jak się okazało – także poszukiwanie liczb pierwszych. Durant zbudował globalny superkomputer, kupując czas przetwarzania od różnych dostawców procesorów graficznych w chmurze. W szczytowym momencie jego projekt sprawdzał prawie 12 razy więcej liczb niż wszystkie inne komputery biorące udział w wyszukiwaniu liczb pierwszych Mersenne’a razem wzięte.
Oprócz użycia masywnego hardware’u w znacznym stopniu zmodyfikowano oprogramowanie do wyszukiwania liczb pierwszych Mersenne’a. Superszybki test Lucasa-Lehmera zastąpiono superszybkim testem prawdopodobnych liczb pierwszych. Po podaniu liczby do sprawdzenia ten nowy test albo potwierdza, że nie jest to liczba pierwsza, albo określa liczbę jako prawdopodobnie pierwszą. Jest bardzo mała szansa, że liczba prawdopodobnie pierwsza okaże się złożoną, więc dopiero po wskazaniu takiej liczby wolontariusze uczestniczący w łowach uruchamiają klasyczny test Lucasa-Lehmera, aby rozwiać wątpliwości. Liczba pierwsza odkryta przez Duranta przeszła test jako prawdopodobna 11 października, a 19 października, rok po rozpoczęciu poszukiwań, niezależne testy potwierdziły znalezienie igły w stogu siana: 2136 279 841–1 to obecnie największa znana liczba pierwsza. Nowa liczba jest dłuższa od dotychczasowej rekordzistki o ponad 16 mln cyfr. Dodatkowo Durantowi przyniosło rozgłos odkrycie największej znanej obecnie liczby doskonałej. Liczby doskonałe to takie, które równe są sumie swoich dzielników mniejszych od samej liczby. Najmniejszą jest 6 (dzieli się przez 1, 2 i 3, a 1+2+3=6), kolejna to 28. XVIII-wieczny matematyk szwajcarski Leonhard Euler udowodnił, że każdej liczbie pierwszej Mersenne’a odpowiada parzysta liczba doskonała, więc znalezienie tej pierwszej oznacza dwa odkrycia w jednym.
Surowca może jednak zabraknąć w każdej chwili, bo nie wiemy, czy liczb pierwszych Mersenne’a – a zatem i parzystych liczb doskonałych – jest nieskończenie wiele. Co ciekawe, nie wiemy też, czy istnieją nieparzyste liczby doskonałe (ten problem bywa uważany za najstarszy nierozwiązany w matematyce).
Zapytany w wywiadzie dla Numberphile na YouTube o koszt poszukiwań, Durant odparł: „Sądzę, że około 2 mln dolarów”. To spora inwestycja w porównaniu z nagrodą oferowaną w GIMPS, która wynosi 3000 dolarów. Zresztą nagrodę tę Durant planuje przekazać szkole średniej, do której uczęszczał – Alabama School of Mathematics and Science.
Można się zastanawiać, dlaczego tak wiele osób poświęca swój czas i pieniądze na poszukiwanie liczb pierwszych, które nie mają praktycznego zastosowania. Częściowo służy to zaspokojeniu ludzkiej ciekawości, a także sprzyja rozwojowi technik obliczeniowych. Ale zapewne najlepszej odpowiedzi udzielił założyciel GIMPS George Woltman, gdy zadano mu to pytanie na kanale Numberphile: „To fajna zabawa”.