Тест Миллера

Ввод: нечетное натуральное n и основание b, где 1 < b < n —1.

Вывод: одно из двух сообщений: «n составное» или «ничего определенного сказать нельзя».

Шаг 1. Последовательно делим n – 1 на 2 пока не получим нечетного частного. В результате найдем положительное целое k≥1 и нечетное q, для которых n – 1 = 2^kq.

Шаг 2. Присвоим i нулевое значение, а r значение вычета b^q по модулю n.

Шаг 3. Если i = 0 и r = 1, или i > 0, а r = n - 1, то вывести сообщение: «ничего определенного сказать нельзя»; в противном случае переходим к шагу 4.

Шаг 4. Увеличиваем i на 1 и заменяем r на r ² по модулю n; переходим к шагу 5.

Шаг 5. Если i < k, то возвращаемся к шагу 3; в противном случае выдаем сообщение: «n составное».

Пример: n = 561, b = 2.

560 = 24 * 35.