Re: big number arithmetic

This discussion reminds me to mention the SPEED (Software Performance
Enhancement for Encryption and Decryption) workshop in Amsterdam, 11-12
July 2007. Topics include software implementation of cryptosystems,
algorithmic speedups, CPU-specific speedups, and more. Submission
deadline for contributed papers is coming up very soon, 6 April. See
http://www.hyperelliptic.org/SPEED for more details on the workshop.

Felix von Leitner writes:
> My naive Karatsuba implementation was slower than my naive schoolbook
> method for 16 word bignums.  I attributed that to it needing to write
> temp bignums, while my schoolbook method just writes to memory once,
> into the result bignum.

Yup, that sounds like a typical Karatsuba slowdown. But the extra costs
disappear if the extra loads and stores are overlapped with the previous
computation.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago