Сначала поясню, почему не подходит тест Миллера-Рабина.
К примеру, мы проверяем на простоту число

.
Если по алгоритму Миллера-Рабина свидетель

выбирается случайно, то не исключена вероятность того, что ГСЧ не выберет

. Если такая вероятность существует, то и достоверно о свойствах проверенного числа сказать ничего невозможно.
Если же мы число проверяем при помощи теста Миллера, то в качестве свидетелей простоты принимаются последовательные числа

.
Допустим, какое-то число мы проверили тестом Миллера. Получен ответ: "число вероятно простое".
Можем ли мы в этом случае
достоверно сказать, что проверенное число является
либо простым, либо числом Кармайкла и никаким иным?
Вот это выделенное меня и интересует.
Если утверждение справедливо, тогда проверив число на делимость на числа от

до

мы могли бы достоверно заявить, что число простое.
То, что

, надеюсь, очевидно.