More on squaring and multiplying large integers

Methods of squaring and multiplying large integers are discussed. The obvious O(n/sup 2/) methods turn out to be best for small numbers. Existing O(n/sup log/ /sup 3/log/ /sup 2/)/spl ap/O(n/sup 1.585/) methods become better as the numbers get bigger. New methods that are O(/sup log5/log/ /sup 3/)/spl ap/0(n/sup 1.465/), O(n/sup log/ /sup 7/log/ /sup 4/)/spl ap/O(n/sup 1.404/), and O(n/sup log/ /sup 9/log/ /sup 5/)/spl ap/O(n/sup 1.365/) presented. In actual experiments, all of these methods turn out to be faster than FFT multipliers for numbers that can be quite large (>37,000,000 bits). Squaring seems to be fundamentally faster than multiplying but it is shown that T/sub multiplyspl les/2T/sub square/+O(n).<>