费马小定理与SICP实现的对应关系是什么？

Question

程序的结构和解释 如此定义费马小定理：

If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

(Two numbers are said to be congruent modulo n if they both have the same remainder when divided by n. The remainder of a when divided by n is also referred to as the remainder of a modulo n, or simply a modulo n.

根据该描述，我编写了以下代码：

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

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

后来，SICP是这样说的：

This leads to the following algorithm for testing primality: Given a number n, pick a random number a < n and compute the remainder of a^n modulo n. If the result is not equal to a, then n is certainly not a prime.

并给出此代码：

(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 是 "a procedure that computes the exponential of a number modulo another number"。

这段代码和费马大定理第一个定义的对应关系我没看懂。我将 "a raised to the nth power is congruent to a modulo n" 理解为：a^n modulo n = a modulo n。但是SICP的代码似乎暗示a^n modulo n = a。 fermat-test 过程中的条件不包括 a modulo n。当然，他们的实施有效，所以我一定是误会了。

请注意，这并不是递归与迭代过程的混淆。

Answer 1

(expt a n) 将计算一个非常大的数字

(expmod a n n) 将计算 0 到 n

范围内的数字

这两个值将是一致的（对 n 取模）。

使用 expmod 的原因是使用它可以使 fermat-test 更快。 fermat-test 函数将给出相同的结果。

Answer 2

测试中的条件是a而不是a modulo n 因为if a < n then a modulo n 是 a，所以 modulo n 是多余的。

他们真正测试的是 n 是否是 Fermat pseudoprime. It doesn't work as a full-fledged test for primality (and SICP doesn't claim that it does) but the ideas involved in the test ultimately lead to the fully practical Miller-Rabin test。

费马小定理与SICP实现的对应关系是什么？

What is the correspondence between Fermat's Little Theorem and the SICP implementation?

math

scheme

sicp