SICP Series-chapter 1.2.6

This section is about prime detection which is a old subject in the history of math.Even in the modern math,prime is still also a popular and interesting subject. But in a long time, number theory is considered as a pure math, which means there is no or little practice value.After entering the information age, the importance of security becomes more and more important.
Here is the code for fast-fermat:
(defun expmod(base e m)
    (cond ((= e 0) 1)
          ((evenp e)
           (rem (expt (expmod base (/ e 2) m) 2) m))
          (t
           (rem (* base (expmod base (- e 1) m)) m))))
 
(defun fermat-test(n)
    (defun try-it(a)
        (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
 
(defun fast-fermat(n times)
    (cond ((= times 0) T)
          ((fermat-test n) (fast-fermat n (- times 1)))
          (T NIL)))

1.21


1.22

1.25
Alyssa’s idea is wrong. If we calculate the number first, the number would be very huge, and program would become slow.
1.26
We can use the trace to monitor the process of a function.

1,27