Modular Exponentiation
eharetea

Modular Exponentiation is an important algorithm in cryptography and computer science.

Modular Exponentiation is an important algorithm in cryptography and computer science.

Date Created:Saturday September 27th, 2008 09:00 PM
Date Modified:Sunday September 28th, 2008 03:12 AM

(define (base-expand n b)
  (if (= n 0)
      '()
      (append
        (base-expand (round (floor (/ n b))) b)
        (list (modulo n b))
      )
  )
)


; n is a list of binary
(define (mod-exp-h b n m k x p)
  (let (
        (power (if (= k 0) (modulo b m) p))
       )
        (if (null? n) 
           x
           (mod-exp-h b (cdr n) m (+ k 1) (if (= (car n) 1) (modulo (* power x) m) x)  (* power power))
        )
   
  )
)

(define (mod-exp b n m) (mod-exp-h b (reverse (base-expand n 2)) m 0 1 0))



Downloads:
Download: mod-exp.scm 535 B

Please login or Click Here to register for downloads
Creative Commons License
Modular Exponentiation by Dan Lynch
is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
Based on a work at www.3daet.com
Permissions beyond the scope of this license may be available at http://www.3daet.com