問題1.27〜問題1.29

問題1.27

　カールマイケル数はフェルマーテストはパスしますが合成数になりました。

(define (carmichael-test n)
  (fermat-chrmichael-test n (- n 1)))

(define (fermat-chrmichael-test n m)
  (cond ((= m 0) true)
        ((= (expmod m n n) m)(fermat-chrmichael-test n (- m  1)))
        (else false)))

(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)))) 

> (carmichael-test 561)
#t
>(carmichael-test 1105)
#t
> (carmichael-test 1729)
#t
> (carmichael-test 2821)
#t
> (carmichael-test 6601)
#t
> (prime? 561)
#f
> (prime? 1105)
#f
> (prime? 1729)
#f
> (prime? 2821)
#f
> (prime? 6601)
#f

問題1.28

(define (mr-test n times)
  (cond ((= n 0) (display 'done))
        ((fermat-test n) (mr-test n (- times 1)))
        (else false)))
        
(define (fermat-test n)
    (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

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

当然カールマイケル数におけるフェルマーテストの実施結果は常に真とは限りません。

> (fermat-test 1105)
#t
> (fermat-test 1105)
#t
> (fermat-test 1105)
#f
> (fermat-test 1105)
#t