Основные отличия между истинными и вероятностными тестами простоты заключаются в том, что истинные тесты выдают точный результат — факт простоты либо составности числа, а вероятностные — дают ответ с некоторой вероятностью. 12

Истинные тесты обладают рядом недостатков, ограничивающих их применение: условность (тест работает лишь для ряда заранее определённых чисел) и малая скорость обработки данных. 3

Вероятностные тесты имеют преимущество перед истинными — высокую скорость обработки данных. 3 Однако в силу вероятности результата ответом могут стать так называемые псевдопростые числа — числа, которые прошли тест на простоту, но таковыми не являются. 3

Многократное повторение вероятностных тестов для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной. 4