Liczby pierwsze

Liczby pierwsze są to takie liczby naturalne, które większe są od jedynki i podzielne bez reszty przez samą siebie i jedynkę. Jednym z pytań dotyczących liczb pierwszych, które narzuca się każdemu 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. 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 (np. P) to iloczyn wszystkich tych P liczb, zwiększony o jedynkę, musiałby być też pierwszy (bo przy dzieleniu przez którąkolwiek z tych P liczb dawałby oczywiście. resztę jeden); zatem przypuszczenie, że jest ich P, 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. Np. 2*3*5+1=31; 31 jest liczbą pierwszą. Nietrudno spostrzec, że ten przepis ma też wady. Nie można nim otrzymać np.: 11,13,17,19,...); po drugie omówiony powyżej zapis konstruowanej liczby trudno uznać za przejrzysty. Dodam jeszcze, ż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 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 liczb pierwszych jest nieskończenie wiele, to może do odnajdywania kolejnych przyda się inny algorytm.
Należy wziąć jakąś liczbę i dzielić ją przez liczby od niej mniejsze których jest prawdopodobnie skończenie wiele jeśli wszystkie liczby podzielą ją z reszty to znaczy że jest to liczba pierwsza. Pomimo że ten algorytm jest poprawny to jest jeszcze bardzo nie efektowny gdyż przy dużych liczbach nawet komputery mogą się pomylić (mowa tu o liczbach posiadających setki tysiące cyfr).

Istnieje jeszcze sposób rozkładania liczby na czynniki pierwsze zwany faktoryzacją polega ona na rozłożeniu liczby na liczby pierwsze (np. 15=3*5, 100=5*5*2*2). Jeśli liczbę da się w taki sposób rozłożyć to nie jest to liczba pierwsza. Ten sposób jest jeszcze bardziej nieefektowny od poprzedniego.

Bardzo starym i znanym sposobem jest “sito Eratostenesa" wypisuje się dowolnej długości ciąg liczb naturalnych zaczynając od dwójki np.: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25... z którego najpierw wykreślamy liczby podzielne przez 2 oprócz dwójki i tak zostaje nam: 2, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25..... następnie przez trzy (bez trójki), przez pięć (bez piątki) zostaje nam 2, 3, 5, 7, 11, 13, 17, 19, 23. I to już mamy same liczby pierwsze mniejsze od dwudziestu pięciu. Biorąc dostatecznie długi ciąg wyjściowy i wykonując czysto mechaniczne eliminowanie (łatwe dla komputera) co drugiej, co piątej i tak dalej “odsiejemy" w efekcie wszystkie liczby pierwsze.

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

W jaki sposób znaleźć więc wielkie liczby pierwsze. Używając niezwykle potężnych i piekielnie drogich superkomputerów Cray z serii T90, wyposażone 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 Graphic`s Cray Research sławna para matematyków David Slowinski - Paul Gage. Szczególnie Slowinski uważany jest za “łowcę" wielkich liczb pierwszych. Ten program jest ważny nie tylko dlatego, że bije rekordy, ale i dlatego, iż jest on cennym narzędziem do testowania każdego nowego modelu superkomputera. Techniki, stosowane do przyspieszenia działania programu wyszukiwania liczb pierwszych, mają duże znaczenie dla rozwiązywania niezwykłej wagi problemów, w rodzaju obliczania pewnych prognoz pogody czy analizy danych, służących poszukiwaniu nowych złóż ropy.

Inny od użycia superkomputera sposób poszukiwania liczb pierwszych polega na zebraniu kilkudziesięciu czy kilkuset przyjaciół i wykonanie tej 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: 2?-1 gdzie n=1398269 ( liczby Mersenne`a są to liczby które da się zapisać w postaci 2?-1 gdzie n musi być liczbą pierwszą; niektóre z nich też są pierwsze. Liczby Mersenne`a dość łatwo poddają się testowaniu). Dokonał tego, używając opracowanego przez George`a Woltmana modyfikacji algorytmu Lucasa-Lehmera i pracując wspólnie z ponad 700 matematykami, komunikującemu się przez Internet. Obecnie w projekcie GIMPS bierze udział już około 2 tysięcy entuzjastów liczb pierwszych. Założyli sprawdzenie wszystkich liczb Mersenne`a o wykładniku mniejszym niż 1345000 jeszcze przed końcem 1997 roku, a do końca 2000 roku chcą sprawdzić wykładniki aż do 2655000. Z początkiem 1996 roku sam Woltman dołączył do zespołu GIMPS. 23 listopada 1996 znaleziono liczbę pierwszą o 420921 cyfrach i jest największą znaną liczbą pierwszą Mersenne`a (35 z kolei) i największą liczbą pierwszą w ogóle.

Liczby pierwsze Mersenne`a są też szczególnie ważne dla kryptografów. Profesor Richard Crandall, szef zespołu