Iterative Square Method in Scheme Language (Scheme 言語による繰り返し自乗法)

gistfile1.scm

;;;
;;; Algorithm: iterative square method
;;; 
;;; Basic Idea: a^(2*n) = (a^2)^n    (mod m)
;;;   e.g. a^4 = (a^2)^2, a^8 = ((a^2)^2)^2, a^16 = (((a^2)^2)^2)^2
;;;
;;; Haskell like code that scans the exponential from LSB to MSB
;;;   pow-mod a 1     m = a mod m
;;;   pow-mod a 2*n   m = powMod (a^2 mod m) n m
;;;   pow-mod a 2*n+1 m = (powMod (a^2 mod m) n m) * a mod m
;;;
(define (pow-mod a n m)       ; a^n mod m
  (cond [(= n 1) (modulo a m)]
        [(even? n) (pow-mod (modulo (* a a) m) (quotient n 2) m)]
        [else (modulo (* a (pow-mod (modulo (* a a) m) (quotient n 2) m)) m)]))

;;;
;;; another code that scans one from LSB to MSB as like as the Horner method
;;;
;;;   pow-mod a n m = horner-pow-mod 1 (list-of (binary-representation-of n))
;;;     where horner-pow-mod acc []     = acc
;;;                          acc (0:xs) = horner-pow-mod (acc^2 `mod` m) xs
;;;                          acc (1:xs) = horner-pow-mod (acc^2 * a `mod` m) xs
;;;
;;; The following is equivalent to above.
;;;   pow-mod a n m = fold-left (λ z x → case x of
;;;                               0 → (z * z `mod` m)
;;;                               1 → (z * z * x `mod` m))
;;;                             1
;;;                             (list-of (binary-representation-of n))
;;;
(require srfi/1)
(define (pow-mod a n m)
  (fold (lambda (x z)
          (case x
            [(#\0) (modulo (* z z) m)]
            [(#\1) (modulo (* z z a) m)]))
        1
        (string->list (number->string n 2))))

;;; another code that uses string-for-each in SRFI 13 or R6RS
(require srfi/13)
(define (pow-mod a n m)
  (let [(z 1)]
    (string-for-each (lambda (x)
                       (case x
                         [(#\0) (set! z (modulo (* z z) m))]
                         [(#\1) (set! z (modulo (* z z a) m))]))
                     (number->string n 2))
    z))