Mention of Fourier transforms over fields other than the complex numbers brought this up to mind: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_

Mention of Fourier transforms over fields other than the complex numbers brought this up to mind: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... TL;DR: It's a way to multiply n-digit integers in time O(n log n * log log n) time, developed in the early 70s, using DFTs in the ring Z mod 2^k + 1, with a slightly clever choice of k. Since the runtime was so tantalizingly close to O(n log n), it fueled speculation that O(n log n) was the optimal runtime. This bound was finally proven in 2019: https://hal.archives-ouvertes.fr/hal-02070778v2 https://hal.archives-ouvertes.fr/hal-02070778v2