Dan's Thoughts Thinking somewhat carefully

(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 (square-mod n m) (remainder (* n n) m))
(define (expmod-iter base n m a)
  (cond ((= n 0) a)
        ((even? n) (expmod-iter (square-mod base m) (/ n 2) m a))
        (else
          (expmod-iter base (- n 1) m (remainder (* a base) m)))))
(define (expmod base n m)
  (expmod-iter base n m 1))