The chord property speeds finite field FFTs
G. Robert Redinbo, K. Krishna Rao · 2005
The number of arithmetic operations needed for a fast finite filed transform is decreased by applying a chord property to the algorithm's intermediate variables. Such a property arises from the conjugacy requirements imposed by the input data lying in a smaller generating field. A chord is a list of conjugate roots which in turn are indexed by cyclotomic subsets of the integers, modulo n. The chords are easily determined through the manipulation of integers, avoiding finite field calculations directly. All transform coefficients falling in the same chord are related by repeatedly forming prime powers of any one of them.