Number-theoretic transforms of prescribed length
Authors:
R. Creutzburg and M. Tasche
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
Full-text PDF
Abstract | References | Similar Articles | Additional Information
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.
- [1] R. C. Agarwal & C. S. Burrus, "Number theoretic transforms to implement fast digital convolution," Proc. IEEE, v. 63, 1975, pp. 550-560. MR 0451632 (56:9914)
- [2]
J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman & S. S. Wagstaff, Jr., Factorizations of
,
up to High Powers, Contemp. Math., vol. 22, Amer. Math. Soc., Providence, R. I., 1983. MR 715603 (84k:10005)
- [3] R. Creutzburg & M. Tasche, "Zahlentheoretische Transformationen und primitive Einheitswurzeln in einem Restklassenring modulo m," Rostock. Math. Kolloq., v. 25, 1984, pp. 4-22. MR 763672 (87f:11003a)
- [4] R. Creutzburg & M. Tasche, "F-Transformation und Faltung in kommutativen Ringen," Elektron. Informationsverarb. Kybernet., v. 21, 1985, pp. 129-149. MR 805046 (87j:43006)
- [5] P. Duhamel & H. Hollmann, "Number-theoretic transforms with 2 as a root of unity," Electron. Lett., v. 18, 1982, pp. 978-980.
- [6]
S. W. Golomb, I. S. Reed & T. K. Truong, "Integer convolutions over the finite field
," SIAM J. Appl. Math., v. 32, 1977, pp. 356-365. MR 0506180 (58:22026)
- [7] R. Lidl & H. Niederreiter, Finite Fields, Addison-Wesley, Reading, Mass., 1983. MR 746963 (86c:11106)
- [8] P. J. Nicholson, "Algebraic theory of finite Fourier transforms," J. Comput. System Sci., v. 5, 1971, pp. 524-547. MR 0286905 (44:4112)
- [9] 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.
- [10] H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithms, Springer, Berlin, 1981. MR 606376 (83e:65219)
- [11] J. M. Pollard, "The fast Fourier transform in a finite field," Math. Comp., v. 25, 1971, pp. 365-374. MR 0301966 (46:1120)
- [12] B. Rice, "Some good fields and rings for computing number-theoretic transforms," IEEE Trans. Acoust. Speech Signal Process., v. 27, 1979, pp. 432-433. MR 540049 (80h:94005)
- [13] B. Richter, "Die Primzahlzerlegung der Werte der Kreisteilungspolynome," J. Reine Angew. Math., v. 254, 1972, pp. 123-132. MR 0302620 (46:1764)
Retrieve articles in Mathematics of Computation with MSC: 94A11, 11T21, 11Y16
Retrieve articles in all journals with MSC: 94A11, 11T21, 11Y16
Additional Information
DOI:
https://doi.org/10.1090/S0025-5718-1986-0856713-1
Keywords:
Number-theoretic transform,
primitive root of unity modulo m,
primitive divisor,
cyclotomic polynomial
Article copyright:
© Copyright 1986
American Mathematical Society