Complexity: $O(k * \log{n})$, где k – число проверок числа а.

Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)

$p \space \text{is prime} \implies a^{p-1} \equiv 1 \space(mod\space n)$

Условие справа является необходимым, но не является достаточным. Что это значит:

1. Если условие справа не выполнено, то число точно составное (как минимум половина чисел $a$ таких, что $1≤a≤\frac{p}{2}$ точно завалят этот тест)
2. Если условие справа выполнено, то число не обязательно простое.

То есть мы не можем быть уверены на 100% в простоте числа (на самом деле, даже если переберём все числа 1 ≤ a < p, числа Кармайкла (Carmichael numbers) проходят этот тест). Однако вероятность ошибки крайне мала и этим можно пренебречь.

Чем больше чисел a проверяем, тем больше вероятность того, что алгоритм выдаст верный ответ.

Классический тест Ферма. Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)

Улучшенный тест Ферма с минимизированной вероятностью ошибки. Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)