Алгоритм теста Ферма для проверки простых чисел заключается в следующем: 1

1. Выбирается случайное число a в диапазоне от 2 до n−1 (число 1 выбирать бессмысленно). 1
2. Если a не взаимно просто с n (это можно быстро проверить с помощью алгоритма Евклида), то n заведомо составное. 1
3. Иначе вычисляется остаток от деления a n−1 на n, и если он не равен 1, то n — составное. 1 Если же равен, то вероятность того, что выбрано «неудачное» a, а для другого a получился бы неединичный остаток, не превосходит 1/2. 1
4. Повторяя алгоритм k раз, каждый раз выбирая случайное a независимо, уменьшают эту вероятность до 1/2k, что очень быстро стремится к нулю с ростом k. 1

Тест Ферма основан на малой теореме Ферма и не даёт гарантированного ответа, но позволяет с высокой вероятностью определить простоту числа. 2