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.

About these ads

Pages: 1 2

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Follow

Get every new post delivered to your Inbox.

Join 644 other followers

%d bloggers like this: