Является ли этот код для теста Миллера-Рабина неправильным? (ответ на упражнение для 1.28 в SICP)

Question

Я пытался решить упражнение 1.28 в SICP о алгоритме Миллера-Рабина, после чего я нашел ответ в Интернете, но я думаю, что ответ был неверным. Я пришел спросить, если это не так.

Он проверяет, если (remainder (square base) m)=1, делая циклы expmod. Однако при выполнении циклов основание и m будут оставаться постоянно, что означает, что он выполняет ту же проверку, а это не то, что хочет сделать тест Миллера-Рабина.

(define (expmod base exp m)
  (cond ((= exp 0)
         1)
        ((nontrivial-square-root? base m) 
         0)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (nontrivial-square-root? a n)
  (and (not (= a 1))
       (not (= a (- n 1)))
       (= 1 (remainder (square a) n))))

если n=k*2^c, думаю, нам стоит проверить, если (remainder (a^(k*2*(c-1))) n)=1.

Answer 1

Это то, что он должен делать. Процедура expmod должна вычислять экспоненту числа по модулю другого числа, единственное отличие на этот раз в том, что вы проверяете нетривиальный квадратный корень каждый раз, когда он повторяется. m будет оставаться постоянным во время процедуры expmod, а написанная вами процедура miller-rabin будет запускать expmod со случайным числом m каждый раз.

Удачного кодирования!

Кстати, удачи в SICP! Я сейчас на тренировке 2.45, становится легче (хотя есть некоторые очень абстрактные понятия).