[GAP Forum] Primitive Root of Unity in Finite Fields

[A.Alecu at lboro.ac.uk]

Dear forum

I have the following problem: I need to implement the Discrete Fourier
Transform on arbitrary finite fields.

Basically starting from a sequence s of period N over a finite field F and
having a primitive n-th root of unity \alpha within that field F, I need to
calculate the transformed sequence S over the extension field of F which
contains all the powers of \alpha. Each term of S is a sum of terms of s
multiplied with powers of \alpha.

Anyway... my problem is (and it might be an easy one) how to find the
primitive n-th root of unity in a finite field?
I noticed that for the complex numbers I could use E(n), I need something
similar for a finite field.

All I have at the moment is a way to find the primitive n-th root of unity
for the cases when n = p^m - 1 where p is a prime and m > 1. For this I use
the PrimitiveRoot(GF(p^m)) which returns the primitive root of the finite
field GF(p^m).

Please can I have your suggestions on how I should solve this problem.

Alternatively could you point me to an existing implementation of the
Discrete Fourier Transform over finite fields.

Thank you for your help in anticipation.

Kind regards,
Alexandra

------
Alexandra Alecu
Research Student

Department of Computer Science
Holywell Park
Loughborough University
Loughborough, LE11 3TU
England
Telephone 	+44 (0)1509 635717
Internal extn 	5720
Fax 	+44 (0)1509 635722
E-mail 	A.Alecu at lboro.ac.uk