Why do we need real numbers for fast convolution on rational numbers?

Question

The superficial answer is "because of the convolution theorem, and converting phasors to cartesian form, and the FFT and $O(n \log n)$," but I want a deeper answer. Is there proof that this is the only way to go about it? How do we know there is no way to perform fast convolution on rational numbers without having to mess with real numbers (i.e. real components of complex numbers)?

Answer 1

There are ways to do fast convolution of integers without leaving the integer domain (without using floating point), for example the Nussbaumer convolution described in the book "Prime Numbers" by Richard Crandall, which achieves the same O(n*log(n)) as the real-based FFT methods.

In practice though (on a computer) the real numbers are quite fast and FFT libraries are optimized and simple to use, and the combination is hard to beat.