Fast Fourier transforms over poor fields. (English) Zbl 1323.68622
Leykin, Anton (ed.), Proceedings of the 36th international symposium on symbolic and algebraic computation, ISSAC 2011, San Jose, CA, USA, June 7–11, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0675-1). 289-296 (2011).
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
algebraic complexity; complexity of polynomial multiplication; fast Fourier transforms; finite fieldsReferences:
| [1] | V. B. Afanassiev and A. A. Davydov. Finite field towers: Iterated presentation and complexity of arithmetic. Finite Fields Appl., 8(2):216-232, 2002. 10.1006/ffta.2001.0337 · Zbl 1037.11088 |
| [2] | A. A. Albert. Fundamental Concepts of Higher Algebra. Univ. of Chicago Press, Chicago, 1956. · Zbl 0073.00802 |
| [3] | G. E. Andrews. Number theory. Dover Pub., 1994. |
| [4] | L. I. Bluestein. A linear filtering approach to the computation of the discrete Fourier transform. Northeast Electronics Research and Engineering Meeting Record, 10:218-219, 1968. |
| [5] | P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory. Springer, 1997. · Zbl 1087.68568 |
| [6] | D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inf., 28(7):693-701, 1991. 10.1007/BF01178683 · Zbl 0766.68055 |
| [7] | S. C. Chan and K. L. Ho. On indexing the prime-factor fast Fourier transform algorithm. IEEE Trans. Circuits and Systems, 38(8):951-953, 1991. |
| [8] | M. Clausen and U. Baum. Fast Fourier Transforms. BI-Wissenschaftsverlag, Mannheim, 1993. · Zbl 0802.65141 |
| [9] | S. D. Cohen. The explicit construction of irreducible polynomials over finite fields. Des. Codes Cryptogr., 2(2):169-174, 1992. 10.1007/BF00124895 · Zbl 0768.11048 |
| [10] | J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex Fourier series. Math. Comp., 19:297-301, 1965. · Zbl 0127.09002 |
| [11] | A. De, P. P. Kurur, C. Saha, and R. Saptharishi. Fast integer multiplication using modular arithmetic. In STOC 2008, pages 499-506. ACM, New York, NY, USA, 2008. 10.1145/1374376.1374447 · Zbl 1231.68289 |
| [12] | M. Fürer. Faster integer multiplication. In STOC 2007, pages 57-66. ACM, New York, NY, USA, 2007. 10.1145/1250790.1250800 · Zbl 1179.68198 |
| [13] | J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, New York, NY, USA, second edition, 2003. · Zbl 1055.68168 |
| [14] | I. J. Good. The interaction algorithm and practical Fourier analysis. J. R. Statist. Soc. B, 20(2):361-372, 1958. Addendum, ibid., 22(2):373-375, 1960. · Zbl 0086.12403 |
| [15] | J. van der Hoeven. The truncated Fourier transform and applications. In ISSAC 2004, pages 290-296. ACM, New York, NY, USA, 2004. 10.1145/1005285.1005327 · Zbl 1064.65158 |
| [16] | D. Jungnickel. Finite Fields: Structure and Arithmetics. Wissenschaftsverlag, Mannheim, 1992. |
| [17] | R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 2008. · Zbl 1139.11053 |
| [18] | H. J. Nussbaumer. Fast Fourier Transform and Convolution Algorithms, volume 2 of Springer Series in Information Sciences. Springer, 1981. · Zbl 0476.65097 |
| [19] | V. Y. Pan. Simple multivariate polynomial multiplication. J. Symb. Comput., 18(3):183-186, 1994. 10.1006/jsco.1994.1042 · Zbl 0831.12004 |
| [20] | A. Pospelov. Faster polynomial multiplication via discrete Fourier transforms. To appear in CSR 2011, volume 6651 of Lecture Notes in Computer Science. Springer, 2011. · Zbl 1330.68121 |
| [21] | F. P. Preparata and D. V. Sarwate. Computational complexity of Fourier transforms over finite fields. Math. Comp., 31(139):740-751, 1977. · Zbl 0365.68053 |
| [22] | C. M. Rader. Discrete Fourier transforms when the number of data samples is prime. Proc. IEEE, 56:1107-1108, 1968. |
| [23] | A. Schönhage. Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf., 7:395-398, 1977. · Zbl 0362.65011 |
| [24] | A. Schönhage and V. Strassen. Schnelle Multiplikation groß er Zahlen. Computing, 7:281-292, 1971. · Zbl 0223.68007 |
| [25] | I. Shparlinski. On finding primitive roots in finite fields. Theoret. Comput. Sci., 157(2):273-275, 1996. 10.1016/0304-3975(95)00164-6 · Zbl 0871.11091 |
| [26] | C. Temperton. Implementation of a self-sorting in-place prime factor FFT algorithm. J. Comput. Phys., 58:283-299, 1985. · Zbl 0609.65099 |
| [27] | L. H. Thomas. Using a computer to solve problems in physics. In Applications of Digital Computers, Ginn and Co., Boston, MA, 1963. |
| [28] | Y. Wang and X. Zhu. A fast algorithm for Fourier transform over finite fields and its VLSI implementation. IEEE J. Sel. Areas Commun., 6(3):572-577, 1988. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
