2

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

为了通过 Miller-Rabin 检验来测试数字n的素数，我们选择一个小于n的随机数a并使用该过程将a提高到( n - 1) st 次幂模数。但是，每当我们在 中执行平方步骤时，我们都会检查是否发现了“ 1模n的非平凡平方根”，即一个不等于1或n - 1的数，其平方等于1模n .expmodexpmod

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

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

这就是我到目前为止所拥有的。

(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))

(define (expmod-signal b n m)
  (define (check a)
    (and (not (= a 1))
         (not (= a (- n 1)))
         (= (square a) (remainder 1 n))))
  (cond ((= n 0) 1)
        ((check b) 0)
        ((even? n) (remainder (square (expmod-signal b (/ n 2) m)) m))
        (else (remainder (* b (expmod-signal b (- n 1) m)) m))))

(define (miller-rabin n)
  (define (fail? n a)
    (or (= n 0) (not (= n a))))
  (define (try a)
    (cond ((= a 1) #t)
          ((fail? (expmod-signal a (- n 1) n) a) #f)
          (else (try (- a 1)))))
  (try (- n 1)))

我认为我实施miller-rabin正确，但我不明白修改后expmod的工作方式。你检查正方形之前的数字还是正方形之后的数字？我不知道从阅读问题。

4

1 回答 1

2

我通过使用expmodinside of的原始定义解决了这个问题expmod-signal。在我的测试中，expmod-signal自然会返回零并弄乱测试。我误解了 check 函数，“其平方等于 1 模 n”表示检查 if a^2 % m = 1。这个检查函数的工作方式是，如果参数是 1 mod n 的非平凡平方根，则返回 0，否则返回参数。如果它返回零，则零传播通过其余部分expmod-signal并返回。

(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))

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

(define (expmod-signal b n m)
  (define (check a)
    (if (and (not (= a 1))
             (not (= a (- n 1)))
             (= (remainder (square a) n) 1))
        0
        a))
  (cond ((= n 0) 1)
        ((even? n) (remainder (square (check (expmod b (/ n 2) m))) m))
        (else (remainder (* b (expmod b (- n 1) m)) m))))

(define (miller-rabin n)
  (define (fail? a)
    (or (= a 0) (not (= a 1))))
  (define (try a)
    (cond ((= a 1) #t)
          ((fail? (expmod-signal a (- n 1) n)) #f)
          (else (try (- a 1)))))
  (try (- n 1)))
于 2019-05-17T02:58:00.000 回答