1994-08-29 - DSPs

Header Data

From: Eric Blossom <eb@comsec.com>
To: karn@toad.com
Message Hash: ef2a2476ce831fab78063592a132fb4a145288617bd7ef3d8cd5eab4c29f4f83
Message ID: <199408292254.PAA02525@comsec.com>
Reply To: <199408262009.NAA17046@unix.ka9q.ampr.org>
UTC Datetime: 1994-08-29 23:36:36 UTC
Raw Date: Mon, 29 Aug 94 16:36:36 PDT

Raw message

From: Eric Blossom <eb@comsec.com>
Date: Mon, 29 Aug 94 16:36:36 PDT
To: karn@toad.com
Subject: DSPs
In-Reply-To: <199408262009.NAA17046@unix.ka9q.ampr.org>
Message-ID: <199408292254.PAA02525@comsec.com>
MIME-Version: 1.0
Content-Type: text/plain

Phil Karn writes:
> But then I hear people say that it's not the multiplication that slows
> down modular exponentiation, it's the modular reduction.

That's one of the driving reasons for using Montgomery multiplication.
You do some up front work that changes the representation into one
where the reduction on each multiply is a multple of 2^N (a shift, or
fetch of the LSW or MSW of the result).

See "Modular Multiplication Without Trial Division", 
Peter L. Montgomery, Mathematics of Computation, v44, n170, pp 519-521,
Apr 1985.