1.28

练习 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的数,其平方根取模n等于1。可以证明,如果1的这种非平凡平方根存在,那么n就不是素数。还可以证明,如果n是非素数的奇数,那么,至少有一半的数a < n,按照这种方式计算 an-1,将会遇到1取模n的非平凡平方根。这也是Miller-Rabin检查不会受骗的原因。请修改expmod过程,让它在发现1的非平凡平方根时报告失败,并利用它实现一个类似于fermat-test的过程,完成Miller-Rabin检查。通过检查一些已知素数和非素数的方式考验你的过程。提示:送出失败信号的一种简单方式就是让它返回 0。

修改后的expmod:

(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (xsquare (expmod base (/ exp 2) m) m) m) ) (else (remainder (* base (expmod base (- exp 1) m)) m) ) ) ) (define (xsquare x n) (if (non-trival-sqrt-exists? n) 0 (* x x))) (define (non-trival-sqrt-exists? n) (non-trival-sqrt-test n 2)) (define (non-trival-sqrt-test n cur) (if (>= cur (- n 1)) #f (if (= (remainder (* cur cur) n) 1) #t (non-trival-sqrt-test n (+ cur 1)) ) ) ) (newline) (expmod 2 3 7) (newline) (expmod 3 2 8) (newline) (expmod 3 8 8) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- n 1)))) ) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- n 1)))) ) (define (timed-prime-test n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (fast-prime? n 5) (report-prime n (- (runtime) start-time)) #f)) (define (report-prime n elapsed-time) (newline) (display n) (display " *** ") (display elapsed-time) (display ", 它的 \\log{n} 倍时间是 ") (display (* elapsed-time (log elapsed-time))) ) (define (timed-prime-test-between n1 n2 found) (if (timed-prime-test n1) (if (or (> found 1) (> n1 n2)) (display " 测试结束! ") (timed-prime-test-between (+ n1 1) n2 (+ found 1)) ) (if (> n1 n2) (display " 测试结束! ") (timed-prime-test-between (+ n1 1) n2 found) ) ) ) (newline) (display "修改后的费马检查表现如下:") (newline) (display "大于 1000 的三个最小素数:") (timed-prime-test-between 1001 9999 0) (newline) (newline) (display "用carmichale数验证效果:") (fermat-test 561) (fast-prime? 561 200)

可以对比练习 1.27,那个版本的 expmod 会导致 561 被识别为素数,但是在这个版本里,它不会。

results matching ""

    No results matching ""