問題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