SICP练习1.28：Miller-Rabin测试中的假阴性

Question

练习1.28。费马测试的一个不能被愚弄的变体称为米勒 - 拉宾测试（Miller 1976; Rabin 1980）。这个 从费马小定理的另一种形式开始，它指出 如果n是质数并且a是小于n的任何正整数，那么上升到（n-1）st次幂是一致的1模ñ。通过米勒 - 拉宾测试对 测试数n的素数，我们选取​​一个 随机数a < n并使用expmod过程将a加到（n-1）st模n。然而，每当我们在expmod中执行平方步骤 时，我们检查是否已经发现了一个“非平凡的正方形 根1模n”，即一个不等于1或n - 1的数，它的正方形为 等于1模n。有可能证明如果存在这样一个非平凡平方根1，那么n不是素数。也可以用 来证明，如果n是不是素数的奇数，那么至少有一半的数字为<n，用这种方式计算^（n-1）将使得 揭示非平凡平方根以1为模n。 （这就是为什么 米勒 - 拉宾测试不能被愚弄的原因。）修改expmod过程为 信号，如果它发现1的平凡平方根并且使用它到 以类似于 的过程实施Miller-Rabin测试-测试。通过测试各种已知素数和非素数来检查你的程序。提示：一个便捷的方式，使expmod信号是有 它返回0

(define (fast-prime? n) 
    (define (fast-prime-iter n counter) 
    (cond ((= counter 1) #t) ; There is no need to check 1 
      ((miller-rabin-test n counter) 
      (fast-prime-iter n (- counter 1))) 
      (else 
      (newline) 
      (display counter) 
      #f))) 
    (fast-prime-iter n (- n 2))) 

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

(define (nontrivial-square-root? val) 
    (if (= val 1) 
    0 
    val)) 

我的想法是过滤掉那些所谓的“1个模n的非平凡平方根”规定的程序nontrivial-square-root?。如果(remainder (square (expmod base (/ exp 2) m)) m)为1，则返回0，在这种情况下，(expmod base (/ exp 2) m)的平方必须等于1模n（这是因为m总是等于n），因此它是非平凡的平方根。

虽然nontrivial-square-root?确实筛选出卡迈克尔数字，如561,1105,1729,2465,2821和6601，但质数如7和13也被报告为复合数据。

是什么导致了这些假阴性？

Answer 1

报价的标有粗体字的重要组成部分：

但是，每当我们执行expmod的平方步骤，我们检查，如果我们已经发现了1个模n的“”平凡的平方根“”那就是，一些不等于1或N - 1其平方等于1个模n

，因此，您广场，走你必须检查其余的参数不是1或n - 1.发生这种情况，例如，如果您致电(miller-rabin-test 5 3)。通过递归处理，您会注意到有一个调用(nontrivial-square-root? (remainder (square 4) 5))，其计算结果为(nontrivial-square-root? 1)。然而，5仍然可以是素数，因为4是5-1。

因此，在平方部分，例如，，调用下面的函数：

(define (sqrmod-with-check val n) 
    (let ((sqrmod (remainder (square val) n))) 
    (cond ((or (= val (- n 1)) (= val 1)) sqrmod) 
      ((= sqrmod 1) 0) 
      (else sqrmod)))) 

这里的参数是expmod通话和m。除了在我们找到1模n的非平凡平方根的情况下，它会为你做平方和余数。当它返回0时，我将它分成三个条件，而不是两个，仅仅是因为可读性。