(module modulararithmetic * ;; export everything
(import scheme)

(define (/-int a b) (floor (/ a b)))

;; base ^ exponent mod n
(define (exptMod base exponent n)
  (define (internalExptMod base exponent result)
    (cond ((< exponent 0) #f)
          ((= exponent 0) (modulo result n))
          ((zero? (modulo exponent 2))
            (internalExptMod (modulo (* base base) n) (/-int exponent 2) result))
          (else
            (internalExptMod (modulo (* base base) n) (/-int exponent 2) (modulo (* base result) n)))))
  (internalExptMod base exponent 1))

) ;; end module

(begin ;; tests
(import scheme
        modulararithmetic)

;; test exptMod
(assert (not (exptMod 2 -1  10)))
(assert (= (exptMod 2  3  10)   8))
(assert (= (exptMod 2  0  10)   1))
(assert (= (exptMod 2  3   5)   3))
(assert (= (exptMod 2  1   5)   2))
) ;; end tests