1.28

secje posted @ 2010年5月17日 05:59 in sicp , 1327 阅读

 

(define (square x) (* x x))
(define (check-one count a m)
  (define (check-1? t)
    (cond ((and (not (= a (- m 1))) (= count 1)) t)
          ((< count 1) t)
          (else 0)))
  (check-1? (remainder (square a) m)))
(define (check-two count a m)
  (define (check-2? t)
    (cond ((and (not (= a 1)) (not (= a (- m 1))) (= count 0)) t)
          ((not (= count 0)) t)
          (else 0)))
  (check-2? (remainder (square a) m)))
(define (expmod base exp m count)
  (cond ((= exp 0) 1)
        ((and (even? exp) (even? (/ exp 2)))
         (check-one count (expmod base (/ exp 2) m count) m))
        ((and (even? exp) (not (even? (/ exp 2))))
         (check-two (- count 1) (expmod base (/ exp 2) m (- count 1)) m))
        (else
         (remainder (* base (expmod base (- exp 1) m count))
                    m))))
(define (prime-test m)
  (define (try-it a)
    (= (expmod a (- m 1) m 1) 0))
  (try-it (+ 1 (random (- m 1)))))
(define (miller-test m times)
  (cond ((= m 1) #f)
        ((= m 2) #t)
        ((even? m) #f)
        ((= times 0) #t)
        ((prime-test m) (miller-test m (- times 1)))
        (else #f)))

这个是了解miller-test之后写的

http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

然后这个是按照书上的要求写的

 

(define (square x) (* x x))
(define (check a n)
  (define (check-1? t)
    (if (and (> a 1)
             (< a (- n 1))
             (= t 1))
        0 t))
  (check-1? (remainder (square a) n)))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (check (expmod base (/ exp 2) m) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))
(define (prime-test m)
  (define (try-it a)
    (= (expmod a (- m 1) m) 1))
  (try-it (+ 1 (random (- m 1)))))
(define (miller-test m times)
  (cond ((= m 1) #f)
        ((= times 0) #t)
        ((prime-test m) (miller-test m (- times 1)))
        (else #f)))

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter