(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m))
        (else (remainder (* base (expmod base (- exp 1) m))
                         m))))

; Runtime is O(exp) not O(log(exp))
; Rather than cutting the problem size in half 1-2 iterations, this procedure
; creates two problems with halve the size.
;
; To see why expmod has linear runtime
; Consider the runtime for exp = n vs 2n
; Let T = the runtime for exp = n
;
; (expmod base 2n modulus) evaluates expmod twice for exp = n
; and does O(1) extra work (e.g. checking if exp is even, computing a product
; and remainder). Thus the runtime is >2T, and expmod has Omega(n) runtime.
;
; Note: g(n) is Omega(f(n)) means g(n) > c*f(n) for some c and all sufficiently
; large n
;
; The recurrences for slow expmod vs fast expmod are:
; T(n) = 2T(n/2) + 1 vs T(n) = T(n/2) + 1
; with solutions
; T(n) is O(n) vs T(n) is O(log(n))