How to use the Fast Fourier Transform in Large Finite Fields

Preprint English OPEN
Petersen, Petur Birgir;
(2011)
  • Subject: 11, 42, 68 and 94 | Mathematics - Number Theory

The article contents suggestions on how to perform the Fast Fourier Transform over Large Finite Fields. The technique is to use the fact that the multiplicative groups of specific prime fields are surprisingly composite.
  • References (10)

    [1] [2] [3] [4] [5] [6] [7] Shuhong Gao, A New Algorithm for Decoding Reed - Solomon Codes, in Communications, Information and Network Security (V. Bhargava, H. V. Poor, V. Tarokh and S. Yoon, Eds.), pp. 55 - 68, Kluwer Academic Publishers, 2003.

    ISBN 978-1-4020-7251-2 T. K. Truong, P. D. Chen, L. J. Wang, Y. Chang, I. S. Reed, Fast prime factor, discrete Fourier algorithms over GF (2m), for 8 ≤ m ≤ 10, Inform. Sci. 176, pp. 1 - 26, 2006.

    T. K. Truong, P. D. Chen, L. J. Wang, Y. Chang, I. S. Reed, Erratum to Fast prime factor, discrete Fourier algorithms over GF (2m), for 8 ≤ m ≤ 10, Inform. Sci. 177, pp. 967 - 968, 2007.

    I. S. Reed, T. K. Truong, R. L. Miller and B. Benjauthrit, Further Results on Fast Transforms for decoding Reed-Solomon Codes over GF(2n) for n = 4, 5, 6, 7, DSN Progress Report 42-50, pp. 132 - 154, January and February 1979.

    James W. Cooley and John W. Tukey, An algorithm for Machine Calculation of Complex Fourier Series, Math. Comp., Vol. 19, pp. 297 - 301, April 1965.

    Richard E. Blahut, Algebraic Codes for Data Transmission, pp. 132 - 133, Cambridge University Press, Cambridge, 2003.

    ISBN 0-521-55374-1 G. D. Bergland, The Fast Fourier Transform Recursive Equations for Arbitrary Length Records, Math. Comp., Vol. 21, pp. 236 -238, April 1967.

    W. M. Gentleman and G. Sande, Fast Fourier Transform for Fun and Profit, AFIPS Proc. 1966, Fall Joint Computer Conf. , Volume 29, pp. 563 - 678, Spartan, Washington DC, 1966.

    Neal Koblitz, A Course of number theory and cryptography, second edition, pp. 34 - 35, Springer-Verlag New York, 1994.

    ISBN 0-387-94293-9

  • Metrics
Share - Bookmark