Multiplying Big Numbers Using FFT

[n+1]

Multiplying big numbers is a very common application of the FFT, and as such, there are many papers on the subject available online.

However, these papers all use sophisticated algorithms where a simple one seems to work. My question is, what's wrong with the simple algorithm:

Multiplication of Two Big Numbers Algorithm:
Input: Two integers, a and b, stored in base B.
Step 1: Write a and b as polynomials in Z[B ], a(B) and b(B).Let m be the the larger of the two degrees.
Step 2: Rewrite a(B) and b(B) as 2m-dimensional vectors by padding with 0s. Denote these vectors by v_a and v_b.
Step 3: Use the FFT and Convolution Theorem to compute the Convolution of v_a and v_b quickly.
Step 4: Recover ab by reversing step 2 and 1.

Complexity Analysis
Let D = Max(a,b). Notice log(D) ~ m.
Step 1: 1. You're just reinterpreting what a list represents.
Step 2: m. You're at most adding 2m zeroes.
Step 3: m log(m).
Step 4: m. You're doing similar operations as in steps 1 and 2.
Conclusion: m log(m) or log(d) log(log(d)).

 

[n+1]

CLRS discusses polynomial multiplication (Chapter 32). They verify that polynomial multiplication using the FFT has complexity n log(n).

I guess my confusion stemmed from talk about "the interpolation of polynomials using roots of unity." Every paper I read talks about this. As far as I can tell, this is just a problem-specific description of the FFT. I don't know why the authors are so eager about adding this extraneous information -- but again, they know way more about the subject than I do. Oh well.