Microprocessor implementation of number theoretic transforms
Consideration is given to the suitability of microprocessor systems for the fast implementation of number theoretic transforms (n.t.t.s). Fast-multiply instructions available on some microprocessors, or the use of external multipliers, relax the basic constraints on the choice of a particular n.t.t. A search was made for suitable moduli which allow fast computation of n.t.t.s using Winograd's algorithm. The search was extended for other moduli which allow increased dynamic range when combined using the Chinese remainder theorem. Finally, a description is given of how modular arithmetic may efficiently be performed using microprocessors