  We show how to improve the efficiency of the computation of fast Fourier
transforms over F_p where p is a word-sized prime. Our main technique is
optimisation of the basic arithmetic, in effect decreasing the total number of
reductions modulo p, by making use of a redundant representation for integers
modulo p. We give performance results showing a significant improvement over
Shoup's NTL library.
