Fast classical and quantum algorithms are introduced for a wide class of non-separable nD discrete unitary K-transforms (DKT)KN(n). They require a number of 1D DKT KN smaller than in the Cooley-Tukey radix-p FFT-type approach. The method utilizes a decomposition of the nD K-transform into a product of original nD Discrete Radon Transform and of a family parallel/independ 1D K-transforms. If the nD K-transform (for example, Discrete Fourier Transform) has a separable kernel, that again in this case our approach leads to decrease of multiplicative complexity by factor of n (where n is the dimension) compared to the row/column separable Cooley-Tukey p-radix approach.