Какое соответствие между Маленькой теоремой Ферма и реализацией SICP?

Question

Структура и интерпретация программ определяет маленькую теорему Ферма таким образом:

Если n - простое число и a - любое положительное целое число, меньшее n, тогда Возвышенная до n-й степени конгруэнтна модулю n.

(Два числа называются конгруэнтными по модулю n, если оба имеют тот же остаток при делении на п. Остаток от деления на п также называется остатком по модулю n или просто по модулю п.

На основании этого описания я пишу этот код:

(define (fermat-test a n) 
  (congruent? (expt a n) a n))

(define (congruent? x y n) 
  (= (modulo x n) 
     (modulo y n)))

Позже SICP говорит:

Это приводит к следующему алгоритму проверки простоты: число n, выберите случайное число a

и дает этот код:

(define (fermat-test) 
  (define (try-it)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

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

, где expmod - это «процедура, которая вычисляет экспоненту числа по модулю другого числа».

Я не понимаю соответствия между этим кодом и первым определением теоремы Ферма. Я понимаю, что "вознесение в n-ую степень соответствует модулю n" как: a^n modulo n = a modulo n. Но код SICP, похоже, подразумевает a^n modulo n = a. Условие в процедуре fermat-test не включает a modulo n. Конечно, их реализация работает, поэтому у меня должно быть недопонимание.

Обратите внимание, это не путает рекурсивные и итеративные процессы.

Answer 1

Условие в тесте имеет a, а не a modulo n, потому что если a < n, то a modulo n равно a, так что modulo n является лишним.

Что они действительно проверяют, так это если n является Ферма псевдослучайным . Он не работает как полноценный тест на первичность (и SICP не заявляет, что это так), но идеи, вовлеченные в тест, в конечном итоге приводят к полностью практическому тесту Миллера-Рабина .

Answer 2

(кроме an) вычислит очень большое число

(expmod ann) вычислит число в диапазоне от 0 до n

, два значения будут конгруэнтными (по модулю n).

Причиной использования expmod является то, что с помощью него можно выполнить намного более быстрый ферма-тест.Функция fermat-test в любом случае даст тот же результат.