The state of the art in multiprecision integer arithmetic is Scho"nhage. Schonhage invented the all-integer Fast-Fourier-Transform based big-int multiplication method. An n-bit can be multiplied in O(n ln n) operations. This is a big improvement over the Karatsuba method which is O(n^1.5) and the classical method O(n^2). Surprisingly, the constant factor isn't that large. This can be combined with modmult techniques for fast modexp routines. However, it's only worthwhile for large numbers (>512 bits). At n=512, if your bigints are stored as polynomials with a 32-bit radix, then N=512/32=16. 16^1.5 = 64, 16 * lg(16) = 64 (so the FFT method and the Karatsuba method are equivalent for numbers of that size) If you are dealing with 2048 or 4096 bit keys, it starts to look attractive. Schonhage published a book in the last year, the result of more than 10 years of research into this area. It's hard to get a hold of though, you have to order it from germany. 95-133299: Schonhage, Arnold. Fast algorithms : a multitape Turing machine implementation / Mannheim : B.I. Wissenschaftsverlag, c1994. x, 297 p. : ill. ; 25 cm.