Implement Karatsuba and 3-way Toom-Cook multiplication of large integers, and improve exponentiation algorithm used in pow().

Karatsuba is a recursive algorithm for multiplying multi precision integers. It has a running time of O(n ^ 1.58) compared to O(n ^ 2) [or O(n * m)] for the "simple" multiplication algorithm. It is discussed in Knuth volume 2 and http://cr.yp.to/papers/m3.pdf as well as other literature.

Anecdotal evidence indicates that Karatsuba is the best multiplication algorithm for numbers of around 500 to a few 1000 bits as are commonly used in cryptographic and other common applications. Therefore, we should consider implementing it in BigInteger.

Toom-Cook 3-way multiplication is also a recursive algorithm for multiplying multi-precision integers that becomes more effective than Karatsuba for integers beyond a larger threshold of number of bits. More information may be obtained here: http://bodrato.it/toom-cook/ http://bodrato.it/papers/#WAIFI2007.

Exponentiation may be improved by factoring out powers of two for left-shifting, and using Karatsuba and Toom-Cook squaring for large numbers.

###@###.### 2003-03-26