> At the root of the fast transform is the simple fact that

Actually... no? That's a constant factor optimization; the second expression has 75% the operations of the first. The FFT is algorithmically faster. It's O(N·log2(N)) in the number of samples instead of O(N²).

That property doesn't come from factorization per se, but from the fact that the factorization can be applied recursively by creatively ordering the terms.

It's the symmetry that gives recursive opportunities to apply the optimization. It's the same optimization folded over and over again. Butterfly diagrams are great for understanding this. https://news.ycombinator.com/item?id=45291978 has pointers to more in depth exploration of the idea.

Well, actually ... Summation is linear time, multiplication is superlinear (eg n log n in number of digits).

Meaning that this takes k summations and one multiplication rather than k multiplications and k summations.

... Where k is the number of terms.