1.2.5 · Проверка на простоту

Проверка простоты и границы ее свидетельства

Перебирайте пробные делители, повторяйте проверки с возведением в степень по модулю и сравните вероятную простоту с числом Кармайкла.

Вопрос для размышления

Что устанавливает каждая процедура проверки простоты и что все еще может оставаться неопределенным после того, как она возвращает true?

Остановка метода пробных делителей, как только проверяемый делитель превышает границу квадратного корня
Подсчет проверенных делителей отдельно от итогового ответа о простоте или составной природе числа
Повторное использование быстрого возведения в степень по модулю в проверке сравнения Ферма
Объединение нескольких выбранных оснований в один результат вероятной простоты
Распознавание числа Кармайкла как контрпримера к наивной уверенности в тесте Ферма

Метод пробных делителей проверяет, делит ли n какое-либо целое число от 2 до границы квадратного корня. Если таких чисел нет, больший нетривиальный множитель не может существовать без меньшей пары. Первая программа подсчитывает только фактически выполненные проверки делителей, поэтому ответ и конечный объем работы остаются отдельными наблюдениями.

Программа Ферма проверяет, сравнимо ли a^n с a по модулю n для выбранного списка оснований. Простое число 7 проходит проверку, составное 15 быстро дает сбой, а составное 561 проходит проверку для трех взаимно простых оснований, хотя метод пробных делителей находит множитель. Отображаемый результат фиксирует решение о вероятной простоте в рамках выбранной процедуры Ферма.

Код SICP527 из 1,048,576 байт UTF-8

(begin
  (define divisor-tests 0)
  (define (divides? divisor n)
    (set! divisor-tests (+ divisor-tests 1))
    (= (remainder n divisor) 0))
  (define (find-divisor n candidate)
    (cond ((> (* candidate candidate) n) n)
          ((divides? candidate n) candidate)
          (else (find-divisor n (+ candidate 1)))))
  (define (measure n)
    (set! divisor-tests 0)
    (let ((divisor (find-divisor n 2)))
      (list n divisor (= n divisor) divisor-tests)))
  (list (measure 29)
        (measure 35)
        (measure 97)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Программа пробных делителей возвращает ((29 29 #t 4) (35 5 #f 4) (97 97 #t 8)). Программа сравнения Ферма возвращает ((prime-7 #t #t) (composite-15 #f #f) (carmichael-561 #f #t)).

На что обратить внимание в трассе

Подсчитайте каждое применение divides? и найдите точку, где квадрат candidate становится больше n. В expmod проследите за делением показателя степени пополам и редукцией по модулю. Для 561 сравните путь метода пробных делителей, находящий множитель, с выбранными путями Ферма, которые возвращают true. Трасса выполнения фиксирует только эти конечные основания.

Попробуйте сами

Измените программу и сравните результат.

Добавьте 1105 в список сравнения, выберите как минимум три взаимно простых с ним основания и сравните результат Ферма с методом пробных делителей. Затем объясните, как каждое дополнительное основание меняет результат вероятной простоты, пока метод пробных делителей дает точную классификацию множителей.

Показать подсказку

1105 также является числом Кармайкла. Сохраните выбранный список оснований видимым в исходном коде и выведите результаты обеих процедур отдельно.

Завершить этот урок

В этой главе пройдено 0 из 18 уроков0%