問題1.27

(5am:test exercise-1.27
  (5am:is-true (complete-fermat-test 3))
  (5am:is-false (complete-fermat-test 4))

  (5am:signals error (complete-fermat-test 0))
  (5am:signals error (complete-fermat-test -1))

  ;; Carmichael numbers
  (5am:is-true (complete-fermat-test 561))
  (5am:is-true (complete-fermat-test 1105))
  (5am:is-true (complete-fermat-test 1729))
  (5am:is-true (complete-fermat-test 2465))
  (5am:is-true (complete-fermat-test 2821))
  (5am:is-true (complete-fermat-test 6601)))

(defun expmod (base exp m)
  (cond ((zerop exp) 1)
        ((evenp exp)
         (mod (expt (expmod base (/ exp 2) m) 2) m))
        (t (mod (* base (expmod base (1- exp) m)) m))))

(defun complete-fermat-test (n)
  (labels ((naturalp (n)
             (or (minusp n) (zerop n)))
           (fermat-test (a)
             (= (expmod a n n) a))
           (rec (a)
             (cond ((zerop a) t)
                   ((fermat-test a) (rec (1- a)))
                   (t nil))))
    (when (naturalp n)
      (error "~a is not natural number." n))
    (rec (1- n))))

テストを実行すると、

> (5am:run! 'exercise-1.27)
..........
 Did 10 checks.
    Pass: 10 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)

NIL

となり、Carmichael数はFermatテストを騙していることが分かる。