1994-08-26 - Re: Fast modular exponentiation

Header Data

From: Phil Karn <karn@unix.ka9q.ampr.org>
To: hfinney@shell.portal.com
Message Hash: 17a63910e632df84938cd9b5492634c21edc908f3dfcfcb6894634d0608ec958
Message ID: <199408260554.WAA16670@unix.ka9q.ampr.org>
Reply To: <199408241507.IAA15669@jobe.shell.portal.com>
UTC Datetime: 1994-08-26 07:05:05 UTC
Raw Date: Fri, 26 Aug 94 00:05:05 PDT

Raw message

From: Phil Karn <karn@unix.ka9q.ampr.org>
Date: Fri, 26 Aug 94 00:05:05 PDT
To: hfinney@shell.portal.com
Subject: Re: Fast modular exponentiation
In-Reply-To: <199408241507.IAA15669@jobe.shell.portal.com>
Message-ID: <199408260554.WAA16670@unix.ka9q.ampr.org>
MIME-Version: 1.0
Content-Type: text/plain


An interesting discussion. Thanks.

How about a basic tutorial on these various modexp algorithms, with
particular attention to how many of each arithmetic operation
(add/subtract/multiply/divide) are needed as a function of the modexp
input parameter sizes?  I don't really understand all the details yet,
especially how they relate to which algorithm is best for a given
machine.

I.e., if I come up with a list of clock counts for each basic
arithmetic instruction, how can I tell which algorithm is probably
best for my machine?

Phil







Thread