W pogoni za rekordem

Bardzo często mówi się, że matematyka jest królową nauk. Sami matematycy dodają, że królową matematyki jest z kolei pewna jej klasyczna dyscyplina, zwana teorią liczb; zaś w teorii liczb najważniejszą rolę odgrywają liczby pierwsze. Badali je najsłynniejsi matematycy świata: Euklides, Gauss, Euler, Sierpiński...

Czym są liczby pierwsze? Być może ­ definicja tego pojęcia uleciała komuś z pamięci; przypomnijmy ją tedy tym skwapliwiej, że jest bardzo prosta. Otóż liczbą pierwszą nazywamy taką liczbę naturalną (a „naturalne" są liczby 1, 2, 3,...), która jest większa od jedynki (a więc w rachubę wchodzą już tylko liczby 2, 3,...) i podzielna bez reszty tylko przez siebie samą i jedynkę. Wszystkie pozostałe liczby naturalne noszą nazwę złożonych; jest ogromnie ważne, iż każda liczba złożona da się przedstawić w postaci iloczynu liczb pierwszych (pamiętacie ze szkoły „rozkładanie na czynniki pierwsze"?), i to tylko w jeden sposób; na przykład: 15 = = 335, 96 = 23232323233 i tak dalej.

Tak, więc, w myśl tej definicji, liczba 2 jest niewątpliwie pierwsza, 3 również: obydwie faktycznie dzielą się tylko przez siebie i przez jedynkę. Inaczej jest z czwórką: wśród jej dzielników jest także liczba 2, ale 5 jest znów liczbą pierwszą, podobnie 7 i 11. Liczby 6, 8, 9, 10 są, naturalnie, złożone.

Liczby pierwsze ­ przy całej prostocie tego pojęcia ­ są przedmiotem mnóstwa zadań, problemów i twierdzeń. Niektóre z tych twierdzeń są niezwykle złożone w dowodzeniu, inne ze sformułowanych dotychczas problemów tak trudne, że ich rozwiązania nie są znane.

ILE JEST LICZB
PIERWSZYCH?

Jednym z pytań, dotyczących liczb pierwszych, które narzuca się każdemu, kto ma, choć odrobinę talentu matematycznego, jest pytanie o liczbę tych liczb: ile ich jest, skończenie wiele czy, wręcz przeciwnie, nieskończenie? Na to akurat znamy odpowiedź od czasów starożytnych: liczb pierwszych jest nieskończenie wiele. Wiedział o tym już w IV w. p.n.e. sam wielki Euklides.

Euklides (ok. 330­ok. 260 p.n.e.)

Innymi słowy, nie istnieje największa liczba pierwsza: dla każdej danej liczby pierwszej możemy znaleźć większą.

Istotnie, gdyby była jedynie skończona liczba liczb pierwszych (powiedzmy, N), to iloczyn wszystkich tych N liczb, zwiększony o jedynkę, musiałby być też pierwszy, (bo przy dzieleniu przez którąkolwiek z tych N liczb dawałby, oczywiście, resztę jeden); zatem przypuszczenie, że jest ich N, jest fałszywe, bowiem znaleźliśmy oto następną.

Ta dość prosta konstrukcja daje również teoretycznie przepis na konstruowanie coraz większych liczb pierwszych; jeśli, powiedzmy, nasza znajomość podobnych tworów ograniczałaby się do liczb 2, 3, 5, to liczba 23335 + 1 = = 31 byłaby też pierwsza. Nietrudno dostrzec, że ten przepis, ­ choć niezły ­ ma swoje wady: po pierwsze, nie daje nam kolejnej liczby pierwszej (proszę zwrócić uwagę, że „uciekły nam" liczby 7, 11, 13, 17, 19,...); po drugie, omówiony wyżej zapis konstruowanej liczby trudno uznać za przejrzysty.

Na marginesie dodajmy, że w ogóle nie istnieje ­ i nie może istnieć ­ żaden „wzór", w zwykłym sensie tego słowa, który by „produkował" wszystkie liczby pierwsze po kolei. Nie oznacza to, iż nie można podać wzorów, które dają nam całą serię takich liczb, dowolnej zresztą długości.

Skoro wiemy już, że liczb pierwszych musi być nieskończenie wiele, to może do odnajdywania kolejnych przyda się inny algorytm, również z kategorii tych, co narzucają się same: weźmy po prostu jakąś wielką liczbę i dzielmy ją po kolei przez wszystkie liczby mniejsze od niej (wystarczy przez mniejsze od pierwiastka kwadratowego z tej liczby; Czytelnik zechce się zastanowić, czemu), których jest z całą pewnością skończenie wiele; nie ulega wobec tego kwestii, iż nasze dzielenia kiedyś będą miały kres, algorytm istotnie jest dobry...

Ba, tylko, że ogromnie nieefektywny. W wypadku liczb naprawdę bardzo dużych jest on skrajnie trudny nawet dla komputera, który „obsługuje" w zwykły sposób liczby tylko z pewnego zakresu; również i te wielkie, to prawda, ­ ale „wielkie" w naszym ludzkim rozumieniu. Liczby „naprawdę bardzo duże" miewają setki tysięcy cyfr i jakiekolwiek „zwykłe" algorytmy w ich wypadku zawodzą. Zresztą z pewnych względów nie jest to złe: cieszą się z tego zwłaszcza specjaliści od szyfrowania. Dużo bardziej, ­ o czym kilka słów dalej ­ cieszy ich fakt, że przypomniany na wstępie rozkład liczby całkowitej na czynniki pierwsze (zwany „faktoryzacją") jest w wypadku wielkich liczb o wiele trudniejszy do uzyskania od stwierdzenia, czy taka liczba jest pierwsza.

Dwaj najsłynniejsi dotychczas łowcy wielkich liczb pierwszych: D. Slowinski i P. Gage. W środku superkomputer Cray T94

Dwa słowa o tym ­ jak trudny. Najszybszy znany do niedawna algorytm faktoryzacyjny, pewien wariant tzw. sita kwadratowego, pozwala rozłożyć na czynniki przeciętną liczbę 200-cyfrową (proszę zwrócić uwagę na załączoną tabelę rekordowych liczb pierwszych!) za pomocą ok. 1023 operacji arytmetycznych. Oznacza to, że pojedyncza maszyna, wykonująca w ciągu sekundy milion iteracji tego algorytmu, potrzebowałaby na takie zadanie 3.7 mld lat. Na szczęście dla polujących na rekordy ­ w wypadku liczb o pewnej szczególnej budowie algorytm ten działa wielokrotnie szybciej. Niemniej przed ledwie ćwierćwieczem z kawałkiem ­ w 1970 roku ­ za wielkie osiągnięcie uznano pomyślny rozkład na czynniki pierwsze pewnej zaledwie 41-cyfrowej liczby; tyle, że tzw. trudnej, czyli niemającej żadnego małego czynnika pierwszego ani właśnie owej szczególnej budowy.

DAVID SLOWINSKI UŻYWA CRAYA

W jaki sposób „ustrzelić" giganta? Pierwszy pomysł to wziąć jakąś „ogromną strzelbę". Wiele poprzednich rekordów w dziedzinie wyszukiwania gigantycznych liczb pierwszych ustanowiono w taki sposób: używając niezwykle potężnych i piekielnie drogich superkomputerów Cray z serii T90, wyposażonych w potężny algorytm Lucasa­Lehmera.

„Patent" na użycie Craya do wyszukiwania kolejnych liczb pierwszych ma przede wszystkim wchodząca w skład specjalnego zespołu Silicon Graphics's Cray Research sławna para matematyków David Slowinski­Paul Gage (proszę obejrzeć załączoną tabelę rekordów). Szczególnie Slowinski ­ matematyk amerykański średniego pokolenia o polskim rodowodzie ­ uważany jest za prawdziwego łowcę rekordów.

George Woltman ma 39 lat, mieszka na Florydzie

Znajdowanie tych liczb przypomina doprawdy szukanie igły w stogu siana ­ powiedział Slowinski reporterom, gdy został po raz kolejny rekordzistą, ­ ale jest nam o tyle łatwiej, że mamy do dyspozycji oszałamiająco szybki komputer i niesłychanie wydajny program. Ten program ­ autorstwa Slowinskiego i Gage'a ­ jest ważny nie tylko, dlatego, że z jego pomocą bije się rekordy, ale i dlatego, iż jest on cennym narzędziem do testowania każdego nowego modelu superkomputera. To prawdziwa tortura dla maszyny ­ powiedział Slowinski ­ ten program rygorystycznie weryfikuje każdy jej element, od logiki procesora, do struktury i działania elementów pamięci oraz zdolności do pracy wielozadaniowej. Dla systemów o wielkiej mocy obliczeniowej nie ma lepszego sprawdzianu poprawności funkcjonowania. Slowinski zwrócił uwagę na fakt, że techniki, stosowane do przyspieszenia działania programu wyszukiwania liczb pierwszych, mają ogromne znaczenie dla rozwiązania niezwykłej wagi problemów, w rodzaju obliczania pewnych prognoz pogody czy analizy danych, służących poszukiwaniu nowych złóż ropy. Slowinski porównał bicie rekordów wielkości liczb pierwszych i doskonalenie odpowiednich programów komputerowych do budowania bolidów formuły I i ich wyścigów na torach samochodowych. Nie ma wielkiego bezpośredniego pożytku z tych monstrów ­ powiedział, ­ ale pewne zastosowane tu pomysły inżynierskie przydadzą się z pewnością do budowy maszyn, za kierownicami, których zasiądziemy Ty i ja.

JOEL ARMENGAUD, SIEĆ i GIMPS

Odmienny od użycia superkomputera sposób poszukiwania liczb pierwszych zasadza się ­ mówiąc najprościej i najdosadniej, ale w tym wypadku odda to istotę sprawy ­ na skrzyknięciu kilkudziesięciu czy kilkuset kolegów i wykonaniu tej ogromnej pracy zespołowo, przy podziale jej na mniejsze fragmenty. Dokładnie na tym polega projekt GIMPS (Great Internet Mersenne Prime Search), w ramach, którego Joel Armengaud jako pierwszy odkrył nową liczbę pierwszą Mersenne'a: 21 398 269­1 (są to liczby, które da się zapisać w postaci
2n­1, gdzie n musi być liczbą pierwszą; niektóre z nich są też pierwsze. Liczby Mersenne'a dość łatwo poddają się testowaniu). Dokonał tego, używając opracowanej przez George'a Woltmana modyfikacji algorytmu Lucasa­Lehmera i pracując wspólnie z ponad 700 matematykami, komunikującymi się poprzez Internet.

Nawiasem mówiąc, część prasy światowej okrzyknęła tę zespołową metodę pracy absolutną nowością; nie jest to taka zupełna prawda, bo już w 1988 roku, czyli 8 lat przed zapoczątkowaniem GIMPS-a, opisano pomysł dwóch matematyków (o nazwiskach Lenstra i Manasse), którzy ­ jeszcze wcześniej ­ wykorzystali jałowy czas pracy pewnej liczby komputerów połączonych systemem poczty elektronicznej do faktoryzacji liczb 116-cyfrowych; za pomocą opisanej metody na okres kilku miesięcy uzyskali sieciowy równoważnik komputera o mocy obliczeniowej 400 MIPS (milionów instrukcji na sekundę).

Obecnie w projekcie GIMPS bierze udział już około 2 tys. entuzjastów liczb pierwszych. Założyli sprawdzenie wszystkich liczb Mersenne'a o wykładnikach mniejszych niż 1 345 000 jeszcze przed końcem 1997 roku, a do końca 2000 roku chcą sprawdzić wykładniki aż do 2 655 000. Trzeba sobie zdawać sprawę z faktu, że jest to zadanie obliczeniowe na miarę milionów godzin pracy pojedynczego komputera z Pentium na pokładzie...

Z początkiem 1996 roku sam Woltman dołączył do zespołu GIMPS. Witryna internetowa tego zespołu oferuje chętnym darmowe oprogramowanie do zwykłych komputerów osobistych, służące do poszukiwania największych liczb pierwszych. Badania te ­ jak powiedzieliśmy ­ były dotychczas domeną użytkowników superkomputerów. Przez jednoczesne użycie wielkiej liczby małych komputerów postawiliśmy znak zapytania nad tezą o przewadze superkomputerów, gdy chodzi o szybkość ­ stwierdził Woltman.

Cóż to za monstrum zostało ustrzelone w tym zespołowym polowaniu! 23 listopada 1996 roku świat obiegła sensacyjna wiadomość: znaleziona liczba pierwsza ma 420 921 cyfr i jest największą znaną liczbą pierwszą Mersenne'a (35. z kolei) i największą liczbą pierwszą w ogóle.

Armengaud jest jednym z przeszło 700 uczestników zespołu, biorących udział w obliczeniach. I choć to on uzyskał ostateczny wynik, zasługa przypada całej grupie. Bez wspólnej pracy wszystkich sukces nie byłby w żaden sposób możliwy.

Owa rekordowa liczba pierwsza, równa ­ jak się rzekło wyżej ­ 21 398 269­1, jest 35. kolejną tzw. liczbą Mersenne'a. Gdyby ją wydrukować, zajęłaby 225-stronicową książkę formatu kieszonkowego (pocketbook). Praca nad jej znalezieniem zajęła samemu tylko Joelowi 88 godzin nieustannych obliczeń z użyciem komputera osobistego, wyposażonego w procesor Pentium 90 MHz; długo, ale proszę to porównać z przytoczonymi wyżej czasami, przed ćwierćwieczem uważanymi za typowe...

Gordon Spence

Poświęciliśmy tyle miejsca owej liczbie, bo to ona była pierwszym „dzieckiem" projektu GIMPS. Obecnie mamy już kolejną latorośl; monstrum jeszcze przeraźliwsze, ale chronologicznie drugie z kolei, a więc dla szerokiej publiczności, uwielbiającej wszelkich liderów, już mniej ciekawe. Ta liczba to 22 976 221­1, liczba Mersenne'a o numerze 36. W sierpniu 1997 roku Gordon Spence, 38-letni Szkot, pracownik firmy Thorn Microvawe Devices Ltd. z Hampshire w W. Brytanii (nawiasem mówiąc, wcale nie żaden matematyk, a... księgowy, tyle że od 10 lat intensywnie zajmujący się komputerami; sam o sobie mówi, że najchętniej używa komputera do... gry w Quake'a), udowodnił, że jest ona liczbą pierwszą. Ma ona 895 932 cyfry, ponad dwukrotnie więcej od znalezionej przez Armengauda. Gdyby ją wydrukować, zajęłaby 450-stronicową książkę typu „kieszonkowca".

Od starożytności badania liczb Mersenne'a są jednym z centralnych punktów teorii liczb jeszcze; pierwszy myślał o nich już Euklides 350 lat p.n.e., choć, oczywiście, nie używał nazwy „liczby Mersenne'a"; francuski zakonnik Marin Mersenne (1588­1648), od którego nazwiska pochodzi nazwa tych szczególnych liczb, wsławił się gruntownym zbadaniem ich właściwości.

NIE TYLKO KRYPTOGRAFOWIE SIĘ CIESZĄ

Poprzednia rekordowa liczba pierwsza, będąca także liczbą Mersenne'a, została ­ jak mówiliśmy ­ odkryta kilka miesięcy wcześniej, jeszcze przy użyciu wspomnianego superkomputera Cray serii T94. Jej współodkrywca, cytowany wyżej David Slowinski, natychmiast potwierdził prawdziwość wyniku Joela Armengauda. I tu ciekawostka: oba zespoły ostro ze sobą konkurowały i zespół Armengauda był podobno o krok od wyprzedzenia Slowinskiego już poprzednim razem; zabrakło dosłownie kilku dni do zakończenia obliczeń. Slowinski ­ który jest, jak widać, prawdziwym „guru" w dziedzinie wielkich liczb pierwszych ­ potwierdził poprawność wyliczeń Spence'a.

Liczby pierwsze Mersenne'a są też szczególnie ważne dla kryptografów. Profesor Richard Crandall, szef zespołu badawczego firmy NeXT, opatentował w swoim czasie system szyfrowania znany jako Fast Elliptic Encryption (Szybkie Kodowanie Eliptyczne), wykorzystujący właśnie te liczby. Program, który odnalazł rekordową liczbę, został oparty na wynikach badań Crandalla, które zagwarantowały z górą dwukrotnie szybszy niż dotychczas przebieg obliczeń.

Współczesne poszukiwania rekordowych liczb pierwszych przy użyciu nowego algorytmu mają, co najmniej trzy interesujące aspekty.

Po pierwsze, stanowią doskonałe ćwiczenie dla młodzieży interesującej się matematyką i komputerami. Pewien nauczyciel matematyki na Florydzie wykorzystuje uczestnictwo w nich jako... nagrodę: po omówieniu na lekcji problematyki liczb pierwszych i pozytywnym zaliczeniu odpowiedniego testu uczeń zyskuje prawo dostępu do szkolnego komputera i udziału w zespole Armengauda.

Po drugie, pomyślny wynik pracy zespołu stanowi dowód zupełnie nowych i niezwykłych możliwości efektywnej współpracy całych setek badaczy, rozproszonych po świecie i korzystających z Internetu. Tanie komputery osobiste, pracujące w czasie normalnie nie wykorzystywanym (na przykład nocami), mogą ­ jak się okazało ­ z powodzeniem rozwiązywać problemy wymagające dotychczas użycia kosztujących miliony dolarów gigantów.

Po trzecie wreszcie, użyty w badaniach program stanowi ­ tak jak i program Slowinskiego dla Craya ­ niezwykłe obciążenie dla komputera osobistego i z tej racji może być doskonałym narzędziem testującym. Rzeczywiście, w trakcie badań Armengauda i zespołu wykryto usterki w ponad 3% maszyn; nie zostałyby one ujawnione w inny sposób. Woltman powiada, że będzie uruchamiał swój program na każdym nowo nabytym komputerze ­ i jeśli wynik obliczeń nie zadowoli go, bez litości zwróci maszynę sprzedawcy.

Poszukiwania liczb pierwszych Mersenne'a nadal trwają. Do projektu GIMPS dołączyć może każdy, kto ma komputer i dostęp do Internetu. Nie trzeba być ani zawodowym matematykiem, ani żadnym komputerowym „guru"; wszystko załatwi dostarczane za darmo oprogramowanie.

Armengaud twierdzi, że uczestnicy tej niezwykłej przygody mogą w ogóle zapomnieć, że ich komputer pracuje.

Warto zwrócić uwagę na jeszcze jedno: otóż, choć odkryta została 35. liczba Mersenne'a, to... jeszcze nie znamy wszystkich poprzednich; nie wiemy mianowicie, czy pierwsze są liczby o numerach 31­34. A oto kolejna ciekawostka: znajomość którejś z liczb Mersenne'a oznacza automatycznie, że uzyskujemy dowód na to, iż pewna (znacznie od niej większa) liczba zasługuje na miano „doskonałej", tzn. jest równa sumie swych mniejszych od niej dzielników; dla przykładu, najmniejszą liczbą doskonałą jest 6 = 1 + 2 + 3; kolejne ­ proszę sprawdzić ­ to 28, 496, 8128. Znał je już Euklides. Otóż w związku z omawianym odkryciem od listopada 1996 roku wiemy, że doskonała jest liczba 21 398 268(21 398 268­1), mająca 841 842 cyfry, zaś od sierpnia 1997 roku także 22 976 221 (22 976 221­1); ile ta liczba może mieć cyfr ­ proszę się zastanowić w ramach pouczającego ćwiczenia...

PS. Zainteresowanych tą tematyką informuję, że nakładem WNT ukazała się niedawno Mała księga wielkich liczb pierwszych amerykańskiego matematyka Paula Ribenboima, jednego z najwybitniejszych obecnie na świecie specjalistów w tej dziedzinie.

Sito Eratostenesa

Oto jak można odnaleźć kolejne liczby pierwsze za pomocą metody, zwanej „sitem Eratostenesa" (Eratostenes z Cyreny, matematyk grecki, III w. p.n.e.):

Wypisujemy dowolnej długości, zaczynający się od dwójki, (dlaczego?), ciąg liczb naturalnych, na przykład taki:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,...

z którego wykreślimy najpierw wszystkie liczby podzielne przez 2 (prócz samej dwójki), czyli co drugą, dostając...

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29,...

potem wykreślimy wszystkie liczby podzielne przez 3 (prócz trójki), czyli co trzecią...

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29,...

potem to samo dla liczb podzielnych przez 5...

2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...

i tu już mamy same liczby pierwsze mniejsze od trzydziestu. Biorąc dostatecznie długi ciąg wyjściowy i wykonując czysto mechaniczne ­ a więc szczególnie łatwe do zrealizowania komputerowego ­ eliminowanie, co drugiej liczby, co trzeciej, co piątej, (co czwartej już nie trzeba, ­ czemu?) i tak dalej ­ wyłonimy („odsiejemy") w efekcie wszystkie liczby pierwsze.

Ta prosta metoda jednak zawodzi w wypadku ciągów o ogromnej długości: i przy jej zastosowaniu obliczenia trwałyby zbyt długo, żeby ten zachęcający algorytm uznać za przydatny.

Algorytm RSA

Jednym z najważniejszych dziś algorytmów szyfrowania (używanych nie tylko do kodowania wiadomości szpiegowskich czy wojskowych, ale i do utajniania korespondencji gospodarczej czy prowadzonej przez Internet korespondencji prywatnej) jest algorytm, RSA, nazwany tak od nazwisk trzech odkrywców ­ Rona Rivesta, Adi Shamira i Leonarda Adelmana. Został on ogłoszony przed około 20 laty i do dziś jest uważany za jeden z najbezpieczniejszych. Nie wnikając w jego szczegóły, (kto chce, znajdzie je opisane przystępnie w Scientific American, v. 237, n. 8, 1977 rok, str. 120­124, w świetnym artykule słynnego Martina Gardnera; głęboka ­ ale i trudna ­ analiza matematyczna tego i innych algorytmów znajduje się w wydanej przez WNT przesławnej „biblii" wszystkich wywiadów świata, Bruce'a Schneiera Kryptografii dla praktyków), podajmy tylko, że do wygenerowania klucza szyfrującego używa się w tym algorytmie dwóch wielkich liczb pierwszych, których iloczyn ­ oczywiście, jeszcze znacznie od tych liczb większy ­ podaje się do publicznej wiadomości. Kto nie zna choćby jednej z liczb wyjściowych ­ nie zdoła w żadnym rozsądnym czasie rozłożyć tego iloczynu na czynniki pierwsze, co jest niezbędne, aby rozszyfrować wiadomość.

Czego jeszcze nie wiemy o liczbach pierwszych?

* Nie wiemy, czy istnieje nieskończenie wiele liczb doskonałych. Nie wiadomo również, czy istnieje choćby jedna liczba doskonała nieparzysta.

* Liczbami bliźniaczymi nazywamy dwie liczby pierwsze, różniące się o 2 (jak 3 i 5, 5 i 7, 11 i 13, 17 i 19...). Nie wiadomo, czy jest ich skończenie, czy nieskończenie wiele.

* Liczbami zaprzyjaźnionymi nazywamy dwie liczby naturalne m i n o tej własności, że suma wszystkich mniejszych od m dzielników tej liczby równa jest n i jednocześnie suma wszystkich mniejszych od n dzielników liczby n równa jest m. Oczywiście, każda liczba doskonała jest zaprzyjaźniona sama ze sobą. Najmniejszą parę liczb zaprzyjaźnionych stanowią 220 i 284. Znanych jest około 8 tys. takich par; nie wiadomo, czy jest ich nieskończenie wiele. Nie znamy również żadnej takiej pary, w której jedna liczba byłaby parzysta, a druga ­ nie.

* Hipoteza Goldbacha (z połowy XVIII w.) orzeka, że każda liczba parzysta większa od dwóch jest sumą dwóch liczb pierwszych; znaleziono mnóstwo takich rozkładów (ściślej: nie znaleziono takiej liczby, która nie dałaby się w ten sposób rozłożyć), ale ­ od około 250 lat! ­ nie wiadomo, czy twierdzenie jest prawdziwe w całej rozciągłości.

To tylko wybrane przykłady związanych z liczbami pierwszymi zagadek, oczekujących na swego Sierpińskiego czy Slowinskiego. Jest takich problemów mnóstwo; to informacja przeznaczona szczególnie dla tych, którzy sądzą, że w matematyce „wszystko już zostało odkryte".

Największe znane dotychczas liczby pierwsze