Od niedawna matematyczny panteon ma nowego członka. 12 października Luke Durant znalazł rekordową liczbę pierwszą. Skala jest wręcz niewyobrażalna, gdyż aby ją zapisać musielibyśmy użyć ponad 41 milionów cyfr.
Czym są liczby pierwsze?
Aby konkretną liczbę nazwać pierwszą musi ona dodatnia, większa od 1 oraz przede wszystkim posiadać dokładnie dwa dzielniki, którymi jest ona sama oraz 1. Najmniejszą a jednocześnie jedyną parzystą liczbą pierwszą jest 2. Dzieli się ona bowiem jedynie przez 1 oraz 2, czyli w tym przypadku samą siebie. Kolejnymi przykładami będzie 3, 5, 7, 11, 13 itd. Przeciwieństwem liczb pierwszych są liczby złożone. Oprócz jedynki i samej siebie posiadają one również inne dzielniki. Np. 6 dzieli się na 1, 2, 3 oraz 6, zatem zaliczymy ją do drugiego zbioru.
Nazewnictwo obu tych grup nie jest przypadkowe. Według podstawowego twierdzenia arytmetyki każdą liczbę złożoną da się przedstawić w postaci iloczynu liczb pierwszych. Korzystając z tej metody, 42 zapiszemy jako 2××3××7. Liczby pierwsze są zatem “budulcem” z którego składają się liczby złożone.
Metody szukania liczb pierwszych
Przy małych wartościach do sprawdzenia ich pierwszości czasem wystarczy wykonać kilka obliczeń w pamięci. W przypadku naprawdę dużych, a tym samym interesujących dla badaczy liczb wymagana jest ogromna moc obliczeniowa oraz specjalne algorytmy. Sprawdzanie pierwszości każdej liczby po kolei byłoby mało wydajne i nieefektywne, zatem opracowano metody trafniejszego doboru obiektu testowego. Popularnym w poszukiwaniach największych liczb pierwszych sposobem jest sprawdzanie pierwszości konkretnych liczb Marsenne’a. Są to liczby w postaci 2x−x−1. Aby wynik takiego równania był liczbą pierwszą, potęga x również musi do tej grupy należeć.
Równie popularne jest losowe generowanie dużej liczby nieparzystej w celu późniejszego sprawdzenia jej pierwszości. Zarówno w tej jak i wcześniej wspomnianej metodzie wykorzystywane są testy bazujące na specjalnie opracowanych algorytmach.
Największa liczba pierwsza
Organizacją zajmującą się poszukiwaniem rekordowych liczb pierwszych jest Great Internet Mersenne Prime Search. Założony w 1996 roku GIMPS korzysta z wielu komputerów rozsianych po całym świecie, których zasoby udostępniane są poprzez specjalne oprogramowanie. Wolontariusze udostępniając swoje jednostki wspólnie tworzą wspólne środowisko o dużej mocy zdolne do wykonywania tak skomplikowanych i obszernych obliczeń.
Ojcem obecnego rekordu jest Luke Durant. Swoją współpracę z GIMPS rozpoczął on w 2023 roku, jednak historia przełomowego odkrycia sięga 6 lat wstecz. Bowiem w roku 2017 Mihai Preda stworzył program pozwalający na szukanie liczb pierwszych za pomocą kart graficznych i udostępnił je wszystkim członkom GIMPS. Luke Durant jako był pracownik NVIDII doskonale znał potencjał GPU, zatem postanowił on połączyć wspomniane oprogramowanie z ogromną mocą obliczeniową wielu kart dostępnych w chmurze. Taka fuzja stworzyła super komputer gotowy na postawione przed nim zadanie. Wirtualna maszyna składała się z tysięcy jednostek rozsianych po 24 centrach danych w 17 krajach. Po roku prób procesor graficzny w Dublinie wpadł na dobry trop i poinformował, że odnaleziona przez niego liczba jest prawdopodobnie pierwsza. Dzień później GPU w teksasie za pomocą testu Lucasa-Lehmera potwierdził jej pierwszość.
Jak sama nazwa wskazuje, Great Internet Mersenne Prime Search skupia się jedynie na wspomnianych liczbach pierwszych Marsenne’a. Najnowszy rekord to 16. największa (na swój czas odkrycia) liczba pierwsza na koncie organizacji. Możemy zapisać ją w postaci M136279841. Takiego nazewnictwa używa się do opisywania liczb Marsenne’a. Zgodnie ze wzorem 2x−x−1, ciąg cyfr obok litery M oznacza potęgę dwójki. Ten zapis, jednocześnie bardzo konkretny, znacznie ułatwia posługiwanie się dużymi liczbami na ograniczonej przestrzeni, którą jest chociażby kartka A4. Aby umieścić na papierze całą liczbę M136279841 potrzebowalibyśmy około 16400 stron. Aż ciężko sobie wyobrazić, że takie monstrum ma tylko dwa dzielniki.
Liczba M136279841 przebiła poprzedniego lidera o ponad 16 mln cyfr. Dla porównania, w gronie 20 największych liczb pierwszych największa różnica pomiędzy kolejnymi rekordami wynosi około 4,9 mln znaków.
Liczby pierwsze w praktyce
Poszukiwania największych liczb pierwszych mogą wydawać się zwykłą próbą bicia kolejnych rekordów. Po części tak właśnie jest. Liczby tak duże jak M136279841 stanowią część pewnego rodzaju matematycznego wyścigu. Przydają się one do badania teorii liczb oraz pozwalają swojemu odkrywcy zdobyć sławę w naukowym środowisku. Dodatkowo, odnalezienie wyjątkowo imponującej liczby pierwszej wiąże się w otrzymaniem nagrody pieniężnej. Znalezisko powyżej 100 mln cyfr gwarantuje przelew w wysokości 150 000 dolarów, natomiast przekroczenie miliarda znaków to aż 250 000 dolarów. Za swoje znalezisko Luke Durant otrzymał “symboliczne” 3000 dolarów.
Nie zdziwi raczej, że informatyka, jako dziedzina oparta w gruncie rzeczy na wszelkich obliczeniach, jest najlepszą przestrzenią do praktycznego wykorzystanie liczb pierwszych. Ten element matematyki kluczowy jest w kryptografii. Podstawą bezpieczeństwa szyfru jest odpowiednia trudność jego złamania. Obecne komputery doskonale radzą sobie z mnożeniem nawet bardzo dużych liczb, jednak proces odwrotny w postaci faktoryzacji, czyli rozkładu na czynniki pierwsze, może być bardzo czasochłonny.
Zgodnie z tą właściwością algorytmy szyfrujące wykorzystują iloczyn dwóch bardzo dużych liczb pierwszych. Ta operacja jest banalna. Widząc jednak sam wynik, nawet przy pomocy potężnej mocy obliczeniowej odnalezienie pierwotnie użytych liczb stanie się niezwykle czasochłonne. Liczby pierwsze są tutaj kluczowe, gdyż zawsze zapewniają jednoznaczny rozkład na czynniki. Wynik powstały z mnożenia dwóch liczb pierwszych zawsze będzie miał dokładnie 4 dzielniki – jedynkę i samą siebie, co zachodzi dla absolutnie każdej liczby, oraz dwa pierwotne czynniki. Chcąc podobny zabieg wykonać z liczbami złożonymi, wynikami faktoryzacji może być wiele różnych par liczb.
