Testem pierwszości nazywamy tak zbudowany algorytm, który ma na celu określenie, czy badana przez niego liczba, to liczba pierwsza, czy złożona. Liczbę taka można znaleźć dość szybko, jednak nie znaleziono dotychczas efektywnego sposobu na rozkład jej na czynniki pierwsze.
Należy sprawdzić wszystkie liczby pierwsze mniejsze od , gdzie
Dlaczego sprawdzać należy tylko liczby pierwsze?
Ponieważ jeżeli sprawdzamy np. liczbę 2, to nie ma sensu sprawdzać każdą jej wielokrotność.
Tak samo dla pozostałych liczb pierwszych mniejszych od n. Jest to jednak długo trwający test. Jego złożoność wynosi, a więc teraźniejsze komputery nie będą w stanie sprawdzić liczby kilkudziesięciu cyfrowe.
Są to różnego rodzaju testy, w których podstawą jest prawdopodobieństwo losowania tak zwanych pechowych liczb. Nie dają one nigdy 100% pewności, jednak są na tyle dobre, że w większości przypadków wystarczają.
Ogólnie w probabilistycznych testach pierwszości należy wylosować jakąś liczbę, która jest mniejsza niż liczba testowana. Można też losować liczby ze specjalnie przygotowanych zbiorów, co polepsza osiągi algorytmów. Wylosowaną liczbę sprawdzamy, czy nie jest np. dzielnikiem liczby n. Procedurę tę należy powtarzć tak długo, aż prawdopodobieństwa złożoności liczby jest bardzo małe - wystarczające.
Bardzo prosty i mimo swoich wad, często wykorzystywany w różnych algorytmach szyfrowania, np. PGP. Opiera się na Małym Twierdzeniu Fermata, które dla k licz złożoność wynosi klog3n. Jeżeli k liczb spełnia to twierdzenie, to liczba najprawdopodobniej jest pierwsza. Istnieją liczby - liczby Carmichaela, które zawsze spełniają warunki testu Fermata, jednak są liczbami złożonymi.
Jest to test, który przy każdym kolejnym kroku daje ½ prawdopodobieństwa wylosowania pechowej liczby, która mogłaby podzielić testowaną liczbę n. Każdy następny krok daje potęgowe malenie prawdopodobieństwa na to, że liczba jest złożona.
Algorytm tego testu ma ciekawą historie rozwoju, mianowicie, stworzony jako test deterministyczny, został przekształcony na probabilistyczny. Dlaczego? Ponieważ opierał się na nieudowodnionej hipotezie Riemanna. Aby mógł być w ogóle użyty należało zmienić go tak, by opierał się na matematyce pewnej - twierdzeniach udowodnionych. Przekształcenia dokonał O. Rabin.
Algorytm może mieć złożoność klog3n, dla szybkiego sposobu potęgowania liczb. Test przy każdej kolejnej próbie daje ¾ szansy na wylosowanie liczby pechowej, co bardzo szybko zmienia prawdopodobieństwo, że liczba jest złożona.
Deterministyczna wersja działa poprawnie w określonym zakresie. Test ten jest najczęściej wykorzystywanym testem w kryptografii.