Test pierwszości – algorytm określający, czy dana liczba jest pierwsza, czy złożona. Nie jest to równoważne znalezieniu jej rozkładu na czynniki pierwsze. W obecnej chwili (2024 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.
Metoda naiwna Najprostszy test pierwszości wygląda następująco: dla danej liczby należy sprawdzić, czy dzieli się ona kolejno przez 2, 3, aż do Jeśli przez żadną z nich się nie dzieli, oznacza to, że jest pierwsza.
Zamiast testować wszystkie liczby do wystarczy sprawdzić podzielność przez liczby mniejsze lub równe
Dowód. Załóżmy, że jest złożona. Wtedy istnieją liczby takie, że oraz Po przemnożeniu nierówności stronami przez otrzymujemy Ale więc Stąd
Kolejne udoskonalenie polega na sprawdzaniu podzielności jedynie przez liczby pierwsze mniejsze lub równe Ich listę łatwo możemy uzyskać metodą sita Eratostenesa. Metoda ta wciąż wymaga wykonania dużej liczby dzieleń, co oznacza, że już dla 50-cyfrowych liczb pierwszych jest niewykonalna na współczesnych komputerach.