Big Modular Exponentiation
August 8, 2014
Since Scheme can handle large integers, we don’t need to use Montgomery multiplication; the expm function of the Standard Prelude is sufficient:
> (define p 34534985349875439875439875349875)
> (define q 93475349759384754395743975349573495)
> (define m (+ (expt 10 9) 7))
> (expm p q m)
735851262
But it will be quicker to use the formulation based on Fermat’s little theorem, although you will be hard-pressed to see the timing difference:
(define (f p q m) (expm (modulo p m) (modulo q (- m 1)) m))
> (f p q m)
735851262
You can run the program at http://programmingpraxis.codepad.org/NDMl4XkI.
Programming Praxis 