This question is inspired by article Alexander Shen "Gauss multiplication trick?" (Russian, "Mathematical Enlightenment", 2019).

*Dasgupta, Papadimitriou, Vazirani, Algorithms* (2008) Ch. 2:

The mathematician Carl Friedrich Gauss (1777–1855) once noticed that although the product of two complex numbers $$(a + bi)(c + di) = ac − bd + (bc + ad)i$$ seems to involve four real-number multiplications, it can in fact be done with just three: $ac$, $bd$, and $(a + b)(c + d)$, since $$ bc + ad = (a + b)(c + d) − ac − bd.$$ ⟨...⟩ this modest improvement becomes very significant when applied recursively.

*Moore, Mertens, The Nature of Computation (2011)*:

The first $O(n^{\log_2 3}$) algorithm for multiplying $n$-digit integers was found in 1962 by Karatsuba and Ofman [447]. However, the fact that we can reduce the number of multiplications from four to three goes back to Gauss! He noticed that in order to calculate the product of two complex numbers, $$(a + bi)(c + di) = (ac − bd) + (ad + bc)i$$ we only need three real multiplications, such as $ac$, $bd$, and $(a + c)(b + d)$, since we can get the real and imaginary parts by adding and substracting these products. The idea of [447] is then to replace $i$ with $10^{n/2}$, and to apply this trick recursively.

Another books explaining "Gauss trick" give references to the *Donald E. Knuth, The Art of Computer Programming, Vol. 2 and 3.* But there are no words "Gauss trick" in Knuth's books.

**Q:** Does this trick really belong to Gauss or this situation is a reminiscence of FFT which was known to Gauss and rediscovered by Cooley and Tukey?

Theoria Residuorum Biquadraticorum, Commentatio Secunda, Sect. 43-44 (for which there seems to be a German translation available online)? $\endgroup$ – student Dec 27 '18 at 17:24