This is somewhat different than the kind of fast multiplication you are looking for.

Yes, but even scalar multiplication is so much faster on a DSP than on most general purpose CPUs that it seems like a definite win. The 486 takes from 13-42 clock cycles to perform a multiply, depending on the operand sizes and number of significant bits in the multiplier. Even if you couldn't keep the pipeline full on a chip like the PowerPC, you'd still be well ahead. But then I hear people say that it's not the multiplication that slows down modular exponentiation, it's the modular reduction. Phil