1

SICP 练习 1.28

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-ZH-11.html#%_thm_1.28

费马测试的一种变体被称为 Miller-Rabin 测试（Miller 1976；Rabin 1980）。这从费马小定理的另一种形式开始，该定理指出如果 n 是质数并且 a 是任何小于 n 的正整数，则 a 的 (n - 1) 次幂等于 1 模 n。为了通过 Miller-Rabin 检验测试数字 n 的素数，我们选择一个随机数 a < n 并使用 expmod 过程将 a 提高到 (n - 1) 次幂模 n。然而，每当我们在 expmod 中执行平方步骤时，我们都会检查我们是否发现了“1 模 n 的非平凡平方根”，即一个不等于 1 或 n - 1 的数，其平方等于1 模数 可以证明，如果存在这样一个 1 的非平凡平方根，则 n 不是素数。如果 n 是一个非素数的奇数，那么，对于至少一半的数字 a < n，以这种方式计算 a^(n-1) 将揭示一个模数为 n 的非平凡平方根。（这就是为什么 Miller-Rabin 测试不能被愚弄的原因。）修改 expmod 过程以发出信号，如果它发现 1 的非平凡平方根，并使用它来实现 Miller-Rabin 测试，过程类似于 fermat-test。通过测试各种已知的素数和非素数来检查你的程序。提示：产生 expmod 信号的一种方便方法是让它返回 0。

我已经编写了自己的解决方案，其结果与此处提供的解决方案一致：

http://community.schemewiki.org/?sicp-ex-1.28

15是一个非素数的奇数，因此对于a从1到的至少一半数字14，我预计计算expmod(a, 14, 15)将显示 1 模 n 的非平凡平方根，这由expmod返回表示0。

但是，这些是我得到的结果：

(expmod 1 14 15)
> 1
(expmod 2 14 15)
> 4
(expmod 3 14 15)
> 9
(expmod 4 14 15)
> 0
(expmod 5 14 15)
> 10
(expmod 6 14 15)
> 6
(expmod 7 14 15)
> 4
(expmod 8 14 15)
> 4
(expmod 9 14 15)
> 6
(expmod 10 14 15)
> 10
(expmod 11 14 15)
> 0
(expmod 12 14 15)
> 9
(expmod 13 14 15)
> 4
(expmod 14 14 15)
> 1

可以看出，这些结果中只有 2 个是0，与预期的至少 7 个相差甚远。

我误解了声明吗？我是一个彻头彻尾的白痴吗？代码错了吗？SICP错了吗？非常感谢。

编辑 1：要求我提供我正在使用的确切代码。就是这样，虽然我本质上只是复制我链接到的解决方案，并使用别名remainder，mod因为这就是我的解释器所说的。

 (define (square x) (* x x))

 (define remainder mod)

 (define (miller-rabin-expmod base exp m) 
   (define (squaremod-with-check x) 
     (define (check-nontrivial-sqrt1 x square) 
       (if (and (= square 1) 
                (not (= x 1)) 
                (not (= x (- m 1)))) 
           0 
           square)) 
     (check-nontrivial-sqrt1 x (remainder (square x) m))) 
   (cond ((= exp 0) 1) 
         ((even? exp) (squaremod-with-check 
                       (miller-rabin-expmod base (/ exp 2) m))) 
         (else 
          (remainder (* base (miller-rabin-expmod base (- exp 1) m)) 
                     m))))

(define expmod miller-rabin-expmod)

(print (expmod 1 14 15))
(print (expmod 2 14 15))
(print (expmod 3 14 15))
(print (expmod 4 14 15))
(print (expmod 5 14 15))
(print (expmod 6 14 15))
(print (expmod 7 14 15))
(print (expmod 8 14 15))
(print (expmod 9 14 15))
(print (expmod 10 14 15))
(print (expmod 11 14 15))
(print (expmod 12 14 15))
(print (expmod 13 14 15))
(print (expmod 14 14 15))

编辑 2：我现在还手动计算了从 1 到 14的所有值的步骤（它总是通过, , , , , ,expmod(a, 14, 15)递归），我确信只有并遇到一个非平凡的平方根 1。所以我倾向于认为 SICP 对此要么是错误的，要么是没有清楚地表达自己。exp = 14exp = 7exp = 6exp = 3exp = 2exp = 1exp = 0aa = 4a = 11

4

4 回答 4

2

SICP 是错误的，因为它使用了错误的 Miller-Rabin 证人定义（参见 Keith Conrad，The Miller-Rabin 检验）。特别是，以下行是错误的：

错误的主张。 也可以证明，如果 n 是一个非素数的奇数，那么，对于至少一半的数字 a < n，以这种方式计算 a^{n - 1} 将揭示一个模 1 的非平凡平方根n.

您可以验证这是错误的，例如当 n = 9 时。

根据上述参考中的定理 2.9，正确的陈述应该是这样的：

正确的主张。 令 n > 1 为非素数的奇数。然后我们可以将 n - 1 写成 (2^e)k 使得 e ≥ 1 并且 k 是奇数。（例如，如果 n = 21，我们可以写成 21 - 1 = 20 = (2^2)·5，所以 e = 2 ≥ 1 并且 k = 5 是奇数。）可以证明至少对于一半的数字 a < n，我们将有 a^k ≢ 1 和 a^k ≢ n - 1 和 a^{2k} ≢ n - 1 和 ... 和 a^{2^{e-1}k} ≢ n - 1 模 n。

因此，对于 n = 21，我们可以证明对于至少一半的数字 a < 21，我们将有 a^5 ≢ 1 和 a^5 ≢ 20 和 a^10 ≢ 20。我们得到下表（所有给定模 21) 的值：

+----+-----+-------+
| a  | a^5 |  a^10 | MILLER–RABIN WITNESS? 
+----+-----+-------+
|  1 |   1 |     1 | NO, a^5 ≡ 1
|  2 |  11 |    16 | YES
|  3 |  12 |    18 | YES
|  4 |  16 |     4 | YES
|  5 |  17 |    16 | YES
|  6 |   6 |    15 | YES
|  7 |   7 |     7 | YES
|  8 |   1 |     1 | NO, a^5 ≡ 1
|  9 |  18 |     9 | YES
| 10 |  19 |     4 | YES
| 11 |   2 |     4 | YES
| 12 |   3 |     9 | YES
| 13 |  13 |     1 | YES
| 14 |  14 |     7 | YES
| 15 |  15 |    15 | YES
| 16 |   4 |    16 | YES
| 17 |   5 |     4 | YES
| 18 |   9 |    18 | YES
| 19 |  10 |    16 | YES
| 20 |  20 |     1 | NO, a^5 ≡ 20
+----+-----+-------+

果然，超过一半的 a < 21（实际上超过 75%）满足所有三个同余 a^5 ≢ 1、a^5 ≢ 20 和 a^10 ≢ 20。（我们称它们为 Miller-Rabin证人；因为他们见证了 n 不是素数的事实。一般来说，许多素性检验依赖于对所有素数都成立的某些性质——如果你证明这样的性质对某个数不成立，那么这个数就不可能是素数。证人越多，素性检验效果越好。）

编辑。只是作为说明素数的一个例子，这里是 n = 13 的表。自然不可能有任何 Miller-Rabin 见证 13 因为它是素数；没有非原始性可以见证。由于 n = 13，我们有 n - 1 = 12 = (2^2)·3，所以 e = 2 ≥ 1 并且 k = 3 是奇数。因此，正如 Keith Conrad 的说明性论文第 1 页所述，所有 a < 13 将至少满足三个同余 a^3 ≡ 1、a^3 ≡ 12、a^6 ≡ 12 中的一个。果然：

+----+-----+-------+
| a  | a^3 |   a^6 | MILLER–RABIN WITNESS? 
+----+-----+-------+
|  1 |   1 |     1 | NO, a^3 ≡ 1
|  2 |   8 |    12 | NO, a^6 ≡ 12
|  3 |   1 |     1 | NO, a^3 ≡ 1
|  4 |  12 |     1 | NO, a^3 ≡ 12
|  5 |   8 |    12 | NO, a^6 ≡ 12
|  6 |   8 |    12 | NO, a^6 ≡ 12
|  7 |   5 |    12 | NO, a^6 ≡ 12
|  8 |   5 |    12 | NO, a^6 ≡ 12
|  9 |   1 |     1 | NO, a^3 ≡ 1
| 10 |  12 |     1 | NO, a^3 ≡ 12
| 11 |   5 |    12 | NO, a^6 ≡ 12
| 12 |  12 |     1 | NO, a^3 ≡ 12
+----+-----+-------+
于 2020-01-21T04:52:08.007 回答
1

从@Memes 的回答中，我继续为它添加了方案代码：

(define (display-all . vs)
  (for-each display vs))

(define (find-e-k n)
  (define (find-e-k-iter possible-k possible-e)
    (if (= (remainder possible-k 2) 0)
        (find-e-k-iter (/ possible-k 2) (+ possible-e 1))
        (values possible-e possible-k)))
  (find-e-k-iter (- n 1) 0))

; first-witness-case-test: (a ^ k) mod n # 1
(define (first-witness-case-test a k n)
  (not (= (expmod a k n) 1)))

; second-witness-case-test: all a ^ ((2 ^ i) * k) (with i = {0..e-1}) mod n # (n - 1)
(define (second-witness-case-test a e k n)
  (define (second-witness-case-test-iter a i k n)
    (cond ((= i -1) true)
          (else (let ()
                 (define witness (not (= (expmod a (* (fast-expt 2 i) k) n) (- n 1))))
                 (if witness
                 (second-witness-case-test-iter a (- i 1) k n)
                 false)))))
  (second-witness-case-test-iter a (- e 1) k n))

(define (miller-rabin-test n)
  (define (try-it a e k)
    (if (and (first-witness-case-test a k n) (second-witness-case-test a e k n))
        (display-all "is not prime, with a = " a "\n")
        (if (< a (- n 1))
            (try-it (+ a 1) e k)
            (display "is prime\n"))))
  (cond ((< n 2) (display "not prime"))
        ((= (remainder n 2) 0) (display "not prime\n"))
        (else (let ()
               (define-values (e k) (find-e-k n))
               (try-it 1 e k)))))
于 2020-09-05T02:50:52.023 回答
0

费马测试的一种变体被称为 Miller-Rabin 测试（Miller 1976；Rabin 1980）。这从费马小定理的另一种形式开始，该定理指出如果 n 是质数并且 a 是任何小于 n 的正整数，则 a 的 (n - 1) 次幂等于 1 模 n。

  • n 是素数，a < n ==> a^(n-1) = 1 (mod n)

为了通过 Miller-Rabin 检验测试数字 n 的素数，我们选择一个随机数 a < n 并使用 expmod 过程将 a 提高到 (n - 1) 次幂模 n。

所以随机选择一个并检查 a^(n-1) = 1 (mod n)。如果不是，那么你知道 n 不是素数。

然而，每当我们在 expmod 中执行平方步骤时，我们都会检查我们是否发现了“1 模 n 的非平凡平方根”，即一个不等于 1 或 n - 1 的数，其平方等于1 模数

这是在讨论在 expmod 函数中添加的额外检查。这可能是你忽略的事情。

可以证明，如果存在这样一个 1 的非平凡平方根，则 n 不是素数。

让我们详细讨论一下。1 的非平凡平方根将是一个数 x，使得 x^2 = 1 (mod n)。并且 x 不是 1 或 -1。

为什么其中之一表明 n 不是素数？

我们知道 x^2 - 1 = (x - 1)(x + 1) 和 (working modulo n) x-1 和 x+1 都不为零，但它们的乘积为零。这意味着我们有一个复合模数，您可以通过取这两个值的 GCD 来分解它。

还可以证明，如果 n 是一个非素数的奇数，那么，对于至少一半的数字 a < n，以这种方式计算 a^(n-1) 将揭示一个模 1 的非平凡平方根n. （这就是为什么 Miller-Rabin 测试不能被愚弄的原因。）

这又是在讨论向 expmod 函数的平方分支添加内部测试。

修改 expmod 过程以发出信号，如果它发现 1 的非平凡平方根，并使用它来实现具有类似于 fermat-test 的过程的 Miller-Rabin 测试。通过测试各种已知的素数和非素数来检查你的程序。提示：产生 expmod 信号的一种方便方法是让它返回 0。

希望有帮助！询问您是否需要更多指导。

于 2019-05-03T14:01:06.403 回答
0

我找到了一篇涵盖该测试的论文，并证明了 2 和 n-2 之间超过一半的值将导致 1 的非平凡平方根。（定理 4.1）

我做了这个代码来仔细检查它

(define (print x) (display x) (newline))

(define (assert p) (unless p (error 'assert-failed)))

(define (power-of-two-split m)
  ;; write m = 2^e k
  (let loop ((e 0) (k m))
    (if (even? k)
        (loop (+ e 1) (quotient k 2))
        (cons e k))))

(define (exp/mod a k n)
  ;; a^k (mod n)
  (cond ((= k 0) 1)
        ((= k 1) (modulo a n))
        (else (modulo (* a (exp/mod a (- k 1) n)) n))))

(define (miller-rabin a n)
  (assert (odd? n))
  (assert (= 3 (modulo n 4))) ;; only handles e=1 case, need to use power-of-two-split for full test
  (let ((k (quotient (- n 1) 2)))
    (exp/mod a k n)))

(define (test n)
  (for ((i (in-range 2 (- n 2))))
    (let ((m (miller-rabin i n)))
      (print `(,i -> ,m squared ,(exp/mod m 2 n))))))

(test 15)

它打印以下结果

(2 -> 8 squared 4)
(3 -> 12 squared 9)
(4 -> 4 squared 1)
(5 -> 5 squared 10)
(6 -> 6 squared 6)
(7 -> 13 squared 4)
(8 -> 2 squared 4)
(9 -> 9 squared 6)
(10 -> 10 squared 10)
(11 -> 11 squared 1)
(12 -> 3 squared 9)

因此，对照米勒拉宾见证人的正式定义，他们实际上都是温特斯：

定义 2.3。对于奇数 n > 1，用 k 奇数写 n − 1 = 2^ek 并选择 a ∈ {1, . . . , n - 1}。我们说 a 是 n 的 Miller-Rabin 证人，如果 in 的所有同余项都是错误的：* a^k = 1 mod n 和 a^{(2^i)k} = −1 mod n for all i ∈ {0 , . . . , e - 1}。

您可以看到“m”列中的值都不是 1，平方列中的值都不是 14。所以它们都是见证人，所以 >50% 是。

执行“check-nontrivial-sqrt1”的代码与 n=3（mod 4）的这种特殊情况无关，因为在这种情况下 e=1。

更新：

我刚刚意识到为什么我们有很多证人但我们并不总是从他们中找到一个平方根：

米勒-拉宾证人背后的想法是找到一个意想不到的 1 mod n 的平方根。这并不总是我们实际发现的，因为素数 n 的前提 an−1 ≡ 1 mod n 可能实际上对于复合 n 不成立。

这是 a^(n-1) (mod n) 的表格，对于 n=15

(2 -> 4)
(3 -> 9)
(4 -> 1)
(5 -> 10)
(6 -> 6)
(7 -> 4)
(8 -> 4)
(9 -> 6)
(10 -> 10)
(11 -> 1)
(12 -> 9)

正如你所看到的，只有两次同余 a^(n-1) = 1 (mod n) 实际上成立。

于 2019-05-03T15:03:13.703 回答