From: collins@newton.apple.com (Scott Collins)
Date: Tue, 16 Nov 93 15:05:56 PST
To: cypherpunks@toad.com
Subject: RSA/MP/FFT speedups?
Message-ID: <9311162302.AA16496@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


Cetin Koc, Professor at Oregon State working with RSA, gave a lecture at
the 93 RSA Data Security Conference on improving RSA performance, where, at
one point, he discounted the efficacy of FFTs for
multiplication/exponentiation of such small numbers (under 2000 bits),
compared to better use of addition chains, separating squaring from
multiplication, and cleaner MP multiplies, etc.

Recently, someone (I can't remember) mentioned in conversation that someone
else (I also can't remember) had very good results with FFTs.  In fact, the
break even point was actually just a few hundred bits.

I would really like to find out: a) who is doing this work; b) is there a
paper; c) some performance figures (test code would be good :-).

If anyone has any pointers, please send them to me in private e-mail.

If anyone else is interested in this topic, please tell me in private
e-mail; I will CC answers to all interested parties, or (if interest
exceeds my CC threshold) post to the list.

Thanks,


Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   5 Infinite Loop, MS 305-2B   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024:669687   catalyst@netcom.com