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)

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)

You can run the program at

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 701 other followers

%d bloggers like this: