Re: Fast modular exponentiation

> But it is pretty unsatisfying to say that the best algorithm "depends" on
> half a dozen variables, and that we can't reliably predict (engineer) a
> solution.
It does seem to come down to that though.  I've spent a bit of time
playing with a couple of versions of Montgomery Mult code plus
other optimisations for modular exponentiation.

What works best depends upon the processor (I was doing C with some
inline assembler for the multiply and divide ops).

I remember that one particular approach worked very well on an
HP 9000/730 and was miserable on anything else I tried (Sparc, 80486,
MIPS R3000, 68030).

There's a really nice survey paper by Cetin Kaya Koc (then of RSADSI) 
called _High Speed RSA Implementation_ which describes various 
optimisations. The references in this are also pretty useful. 

Mark

-- 
Mark Henderson markh@wimsey.bc.ca - RIPEM MD5: F1F5F0C3984CBEAF3889ADAFA2437433
ViaCrypt PGP key fingerprint: 21 F6 AF 2B 6A 8A 0B E1  A1 2A 2A 06 4A D5 92 46
low security key fingerprint: EC E7 C3 A9 2C 30 25 C6  F9 E1 25 F3 F5 AF 92 E3
cryptography archive maintainer -- anon ftp to ftp.wimsey.bc.ca:/pub/crypto

Mark C. Henderson writes
> There's a really nice survey paper by Cetin Kaya Koc (then of RSADSI) 
> called _High Speed RSA Implementation_ which describes various 
> optimisations. The references in this are also pretty useful. 

So where do we find this survey paper?


-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com