>Aside from the fact the we need to do a single FFT instead
>of two, why isn't squaring inherently faster than multiplying?
I would have said "two instead of three".
The problem is to represent the number in a space in which the computation
of the multiplication is efficient. The FFT do that. But then what we just
need to do is to multiply digits term by term. It is not different of an
addition with the standard number representation, and 2.A is not really
faster to compute than A+B.
But it is possible that today the squaring is not faster than the
multiplying because the squaring by FFT is not the faster algorithm!
Yves
