Based on skimming the paper (finally a proper explanation that gives some hint at intuition), the path to openai's formulation if you're familiar with undergrad CS is (apparently):
* Start with the usual FFT convolution for polynomials, viewing integers as a polynomial in a given base evaluated at a certain point
* In undergrad you (hopefully) saw polynomial multiplication can be done in nlogn via convolution using FFT, but that assumes complex integer addition/multiplication is O(1). Here we need O(log x) bits to simply represent a number x on a real machine.
* If you use naive (n^2) multiplication for those butterfies, then you end up with O(n[(log n)^2]).
* If you recursively use FFT for the digit multiplication at those butterflies, then you get something like O(n[(log n)^(log log n)]).
* Schonhage-Strassen realized that instead of doing FFT in C where the butterfly involves multiplying by \omega (\omega being roots of unity), you can work in a different ring where 2 is a root of unity and so it's a cheap bitshift, but were constrained in how finely they could break subproblems (could only break an n-bit integer into sqrt-n subpproblems each of sqrt-n bits), resulting in an overall O(nlogn * loglogn).
* The 2019 O(nlogn) version (supposedly, this is out of my depth) found a way to use some technique of "Gaussian Resampling" to do the matrix convolution via _multidimensional FFT_ in a ring where multiplying by root of unity became cheap _and_ subproblems could be finer. The bottleneck was thus only the addition/subtraction in the O(log n) butterfly layers, each of which does O(n) work for total of O(n logn)
* OpenAI's paper uses a fact that it's apparently easier to compute multiple butterfly layers "simultaneously" than doing them one at a time independently (page 10). There is some sort of implicit reuse because the later layers mix the outputs of earlier layers, and they take advantage of this to avoid having to write out layer 1 outputs separately from layer 2 outputs, and instead work in some coordinate system where they can intermingle them. This apparently amortizes to some tiny fractional epsilon shaved off of a layer, and since the whole FFT is recursive they can apparently save a factor of (1 - epislon)^(log log n) overall across "log log n" recursion depth, which is apparently where that ridiculously small overall exponent comes from.
It's interesting that in terms of practical implementations, since each multiply can be done as a series of bit-shifts and additions, and since each element of an FFT is just the solution of a polynomial (a series of multiply-accumulates), in theory it's theoretically possible to do a full FFT in a single cpu clock cycle, much as it's possible to do a single multiply or multiply-accumulate in a single clock cycle (via parallel shift-accumulate operations). It would take a ridiculous number of transistors to implement though.
Whether something can be done in a single clock cycle is not useful to know, because this does not say how long is that clock cycle.
A useful performance measure for the evaluation of a function in hardware is the latency of the operation expressed as a multiple of the delay through some standard simple logic gate, e.g. the FO4 delay (of an inverter with a fan-out of 4) that is frequently used in CMOS technology.
While a multiplication can be done in a single clock-cycle if you choose so, the duration of that clock cycle in FO4 delays increases with the size of the numbers that are multiplied, and it is interesting to know how fast it increases with a given multiplication algorithm.
If a multiplication algorithm that claims to be faster when expressed in some abstract operations leads to a FO4 delay number that actually grows faster with the length in bits of the operands, than that algorithm is worse in practice.