Number theoretic transforms over the golden section quadratic field

A new number theoretic transform (NTT) over the real quadratic field Q(√5) is suggested and analyzed. Conventional NTTs are used for fast convolution of integer sequences. A new approach for computing number theoretic transforms (NTTs) is proposed, allowing real signals to be processed as well. The method is based on a Diophantine approximation of the input real signal before the NTT. The choice of the three parameters characterizing any NTT-modulus, transform length, and primitive element-is discussed in detail. From a practical point of view, the suggested NTTs offer attractive combinations of these parameters. Much care has been exercised to reduce the computational complexity. The practical usefulness of an irrational number system is demonstrated. Extensions and open problems are discussed