Number-theoretic transforms of prescribed length
HTML articles powered by AMS MathViewer
- by R. Creutzburg and M. Tasche PDF
- Math. Comp. 47 (1986), 693-701 Request permission
Abstract:
A new constructive method for finding all convenient moduli m for a number-theoretic transform with given length N and given primitive Nth root of unity modulo m is presented. This method is based on the prime factorization of cyclotomic polynomials with integer-valued argument or on the primitive divisors of integers. Many known results can be obtained as simple corollaries.References
- Ramesh C. Agarwal and C. Sidney Burrus, Number theoretic transforms to implement fast digital convolution, Proc. IEEE 63 (1975), no.Β 4, 550β560. MR 0451632
- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603
- Reiner Creutzburg and Manfred Tasche, Zahlentheoretische Transformationen und primitive Einheitswurzeln in einem Restklassenring modulo $m$, Rostock. Math. Kolloq. 25 (1984), 4β22 (German). MR 763672
- Reiner Creutzburg and Manfred Tasche, $F$-Transformation und Faltung in kommutativen Ringen, Elektron. Informationsverarb. Kybernet. 21 (1985), no.Β 3, 129β149 (German, with English and Russian summaries). MR 805046 P. Duhamel & H. Hollmann, "Number-theoretic transforms with 2 as a root of unity," Electron. Lett., v. 18, 1982, pp. 978-980.
- S. W. Golomb, I. S. Reed, and T. K. Truong, Integer convolutions over the finite field $\textrm {GF}(3\cdot 2^{n}+1)$, SIAM J. Appl. Math. 32 (1977), no.Β 2, 356β365. MR 506180, DOI 10.1137/0132029
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- Peter J. Nicholson, Algebraic theory of finite Fourier transforms, J. Comput. System Sci. 5 (1971), 524β547. MR 286905, DOI 10.1016/S0022-0000(71)80014-4 H. J. Nussbaumer, "Relative evaluation of various number theoretic transforms for digital filtering applications," IEEE Trans. Acoust. Speech Signal Process., v. 26, 1978, pp. 88-93.
- Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR 606376
- J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365β374. MR 301966, DOI 10.1090/S0025-5718-1971-0301966-0
- Bart Rice, Some good fields and rings for computing number-theoretic transforms, IEEE Trans. Acoust. Speech Signal Process. 27 (1979), no.Β 4, 432β433. MR 540049, DOI 10.1109/TASSP.1979.1163258
- Bernd Richter, Die Primfaktorzerlegung der Werte der Kreisteilungspolynome, J. Reine Angew. Math. 254 (1972), 123β132 (German). MR 302620, DOI 10.1515/crll.1972.254.123
Additional Information
- © Copyright 1986 American Mathematical Society
- Journal: Math. Comp. 47 (1986), 693-701
- MSC: Primary 94A11; Secondary 11T21, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-1986-0856713-1
- MathSciNet review: 856713