Fast algorithm for computing a primitive /2 to power p + 1/p-th root of unity in GF/q squared/

Abstract

A quick method is described for finding the primitive (2 to power p + 1)p-th root of unity in the Galois field GF(q squared), where q = (2 to power p) - 1 and is known as a Mersenne prime. Determination of this root is necessary to implement complex integer transforms of length (2 to power k) times p over the Galois field, with k varying between 3 and p + 1.