Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Journals Home Search My Subscriptions Subscribe
Previous issue | This issue | Most recent issue | All issues (1943–Present) | Next issue | Previous article | Articles in press | Recently published articles | Next article
Request Permissions
 
 

 

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.

References [Enhancements On Off] (What's this?)

  • [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 $ {b^n} \pm 1$, $ b = 2,3,5,6,7,10,11,12$ 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 $ {\text{GF}}(3 \cdot {2^n} + 1)$," 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)

Similar Articles

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

American Mathematical Society