Возведение в степень по модулю через остатки
Вычисление остатка после каждого умножения держит результат по модулю, пока возведение в квадрат уменьшает показатель. Это основа проверки Ферма.
Что одно сравнение по модулю может установить для числа-кандидата, а чего оно установить не может?
- Уменьшение каждого промежуточного результата возведения в квадрат или умножения по модулю
- Деление четных показателей степени пополам с помощью повторного возведения в квадрат
- Вычисление сравнения Ферма с фиксированным основанием для конечных кандидатов
- Сравнение выполнения сравнения с классификацией методом пробного деления
expmod следует тому же сокращению показателя степени, что и быстрое возведение в степень, но применяет remainder после каждого возведения в квадрат или нечетного умножения. Уменьшенный результат остается сравнимым с исходной степенью по модулю modulus, поэтому окончательный остаток сохраняется без необходимости вычислять полную степень.
passes-base-2? проверяет, сравнимо ли число 2 в степени candidate с 2 по модулю candidate. Проверка проходит для 17 и не проходит для 15. Она также проходит для 561, хотя 561 равняется 3, умноженному на 11 и на 17. Каждый результат точно фиксирует сравнение по основанию 2, в то время как пробное деление дает классификацию составного числа.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Модульное возведение в степень возвращает 3. Проверки с фиксированным основанием возвращают (#t #f #t) для 17, 15 и составного числа 561.
Проследите, как каждый четный показатель степени приводит к вызову с половинным размером перед тем, как его остаток возводится в квадрат и сокращается. Во втором запуске разделите три конечных вызова и наблюдайте, как возвращенные булевы значения сообщают точный результат сравнения по основанию 2.
Измените программу и сравните результат.
Добавьте candidate со значением 21 во вторую программу. Выполните ту же проверку по основанию 2, затем объясните, почему ложный результат разрешает это сравнение, тогда как истинный результат все еще не доказывает простоту числа.
Показать подсказку
Тест проверяет одно точное равенство. Выполнение этого равенства не исключает составные числа, такие как 561.