Carmichael数がフェルマーテストをクリアしてしまうことをかくにんします。
フェルマーテストは整数に関して、[tex:a
(use srfi-19) (define (square x) (* x x)) (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 (carmichael-test n) (define (sub-carmichael-test n a) (cond ((= a 0) #t) ((= (expmod a n n) a) (sub-carmichael-test n (- a 1))) (else #f))) (sub-carmichael-test n (- n 1)))
1729はCarmichael数ですが、
gosh> (carmichael-test 1729) #t
こんな感じで、フェルマーテストをクリアしてしまう。