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 ----- End forwarded message ----- _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
