Mod Exp uses the binary algorhtim.

Definition

;;Definition : A natural number n is either 0,
;;or of the form 2m, or of the form 2m + 1,
;;where m is a natural number.

Help functions

;;mod-aux : number number -> number
;;a aux function to modify the "r" into the 
;;regular form of a remainder
;;example : (mod-aux 5 3) => 2
;;          (mod-aux 2 3) => 2
(define (mod-aux r m)
  (cond
    [(< r m) r]
    [else
     (mod-aux (- r m) m)]))
 
;;mod : number number -> number
;;to calculate the result when n modulo the modulus m
;;example : (mod 15 3) => 0
;;          (mod 17 3) => 2
(define (mod n m)
  (cond
    [(< n m) n] ;if n<m then n is the remainder
    [else
     (cond
       [(= (remainder n 2) 0) ;if n is the form of 2k
        (mod-aux 
         (* 2 (mod (quotient n 2) m)) m)]
       ;because 2r = 2k mod m, where r = k mod m
       [else                 ;if n is the form of 2k+1
        (mod-aux
         (+ 1 (* 2 (mod (/ (- n 1) 2) m))) m)])]))
       ;because 2r+1 = 2k+1 mod m, where r = 2k+1 mod m

;;mod-exp : number number number -> number
;;use the "bin-natural-number" definition
;;to calculate the result of raising the 
;;base x to the exponent n modulo the modulus b.
;;example : (mod-exp 3 4 10) => 1 because 1 = 3^4 mod 10
;;          (mod-exp 2 100 3) => 1 because 1 = 2^100 mod 3
(define (mod-exp x n b)
 (mod (expt x n) b))

(define (squre x)
  (* x x))
 
(define (mod-exp x n m)
  (cond
    [(= n 1)
     (remainder x m)]
    [(odd? n)
     (remainder (* (squre (mod-exp x (quotient n 2) m))
                   (remainder x m))
                m)]
    [else
     (remainder (squre (mod-exp x (quotient n 2) m)) m)]))