Liczby pierwsze

Badaniami nad liczbami pierwszymi zajmowali się już starożytni, z czasem powstało wiele testów, które umożliwiają ich szybką weryfikację.

Tablica liczb pierwszych

Tablica zawiera liczby pierwsze z zakresu 0-100.

Testy na potwierdzenie liczb pierwszych

Testy na potwierdzenie liczb pierwszych dotyczą oczywiście większych cyfr. Podobnych testów jest wiele. Do najbardziej znanych należy test Millera-Rabina, jest to test pierwszości, czyli algorytm mający wykazać powyższe. Należy do tak zwanych testów probabilistycznych, które są powiązane z liczbami losowymi (korzystanie z generatora liczb losowych). Pierwszą jego wersję skonstruował Gary L. Miller w 1976 roku, była to wersja deterministyczna, nie do końca sprawdzona, stąd 4 lata później udoskonalił ją Michael O. Rabin, izraelski informatyk urodzony w przedwojennym Wrocławiu (cała jego rodzina wyjechała do Palestyny niedługo po dojściu Hitlera do władzy w Niemczech). Uważa się, że test Millera-Rabina jest najlepszy z wielu podobnych i daje największe prawdopodobieństwo określenia poszukiwanych liczb. To w zasadzie nowocześniejsza wersja innego, niegdyś bardzo popularnego testu, nazywanego testem Solovaya-Strassena, opracowanego w 1977 roku przez wymienionych w jego nazwie matematyków pochodzących kolejno z USA i Niemiec. Test ten także jest probabilistyczny i ma za zadanie określić, czy liczba jest złożona, czy prawdopodobnie pierwsza. To właśnie ten test udowodnił przydatność praktyczność kryptosystemu RSA. Pomiędzy wersją deterministyczną a probabilistyczną znajduje się test Baillie-PSW (pierwszy człon „dedykowany” jest Robertowi Baillie, zaś skrót PSW to inicjały nazwisk Carla Pomerance'a, Johna Selfridge'a i Samuela Wagstaffa). Odkrycie, czy istnieje liczba złożona spełniająca warunki testu Baillie-PSW to jeden z nierozwiązywalnych problemów matematycznych (aczkolwiek twórcy testu zarzekają się, że takie na pewno istnieją). Najprostszym i bardzo często stosowanym testem jest test pierwszości Fermata, mający charakter probabilistyczny. Dał on impuls do powstania kilku innych testów bardziej złożonych, w tym wymienionemu powyżej testowi Baillie-PSW. Ma wiele wad (często uznaje tak zwane liczby Carmichaela za liczby pierwsze, tymczasem są one złożone), ale i tak to on używany jest do szyfrowania PGP (Pretty Good Privacy, narzędzie do szyfrowania, odszyfrowywania plików, partycji, poczty elektronicznej).
Nie wiemy, jakie były pierwsze testy pierwszości, a przecież o liczbach pierwszych pisał nie tylko Euklides, który stwierdził, że jest ich nieskończenie wiele, ale i przed nim matematycy egipscy, co można wyczytać w tak zwanym papirusie Rhinda. Na pewno najbardziej znane było sito Eratostenesa, które przecież do dziś jest w użyciu (w oryginale Eratostenes z Cyreny korzystał w nim z liczb nieparzystych, a nie pierwszych). Współczesną, udoskonaloną wersją sita Eratostenesa jest sito Atkina, nazywane też sitem Atkina-Bernsteina, algorytm wyszukujący liczby pierwsze w dużych przedziałach.