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.