时间戳

首页 > 解决方案 > 费马小定理与 SICP 实现有什么对应关系？

math - 费马小定理与 SICP 实现有什么对应关系？

问题描述

程序的结构和解释这样定义了费马小定理：

如果 n 是素数并且 a 是小于 n 的任何正整数，则 a 的 n 次幂等于模 n。

（如果两个数在除以 n 时具有相同的余数，则称它们为模 n 一致。a 除以 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 < n 并计算 a^n 模 n 的余数。如果结果不等于a，那么n肯定不是素数。

并给出以下代码：

(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 的 n 次幂与模 n 一致”理解为：a^n modulo n = a modulo n. 但 SICP 的代码似乎暗示a^n modulo n = a. 程序中的条件fermat-test不包括a modulo n。当然，它们的实现是有效的，所以我一定是误解了。

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

标签： mathschemesicp

解决方案

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

他们真正测试的是是否n是Fermat 伪素数。它不能作为一个完整的素数测试（SICP 也没有声称它确实如此），但测试中涉及的想法最终导致了完全实用的Miller-Rabin 测试。

推荐阅读