Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Parameter determination for complex number-theoretic transforms using cyclotomic polynomials

Authors: R. Creutzburg and M. Tasche
Journal: Math. Comp. 52 (1989), 189-200
MSC: Primary 11T06; Secondary 11A07, 11Y40, 65E05, 94A11
MathSciNet review: 946602
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Some new results for finding all convenient moduli m for a complex number-theoretic transform with given transform length n and given primitive nth root of unity modulo m are presented. The main result is based on the prime factorization for values of cyclotomic polynomials in the ring of Gaussian integers.

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

  • [1] 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)
  • [2] R. Creutzburg, Finite Signalfaltungen und finite Signaltransformationen in endlichen kommutativen Ringen mit Einselement, Dissertation, Wilhelm-Pieck-Universität Rostock, 1984.
  • [3] R. Creutzburg & M. Tasche, "F-Transformation und Faltung in kommutativen Ringen," Elektron. Informationsverarb. Kybernet., v. 21, 1985, pp. 129-149. MR 805046 (87j:43006)
  • [4] R. Creutzburg & M. Tasche, "Number-theoretic transforms of prescribed length," Math. Comp., v. 47, 1986, pp. 693-701. MR 856713 (87i:94004)
  • [5] E. Dubois & A. N. Venetsanopoulos, "The generalized discrete Fourier transform in rings of algebraic integers," IEEE Trans. Acoust. Speech Signal Process., v. 28, 1980, pp. 169-175. MR 563379 (81f:12013)
  • [6] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1954. MR 0067125 (16:673c)
  • [7] J. H. McClellan & C. M. Rader, Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Cliffs, N. J., 1979. MR 723867
  • [8] T. Nagell, Introduction to Number Theory, Wiley, New York, 1951. MR 0043111 (13:207b)
  • [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-Verlag, Berlin, 1981. MR 606376 (83e:65219)
  • [11] I. S. Reed, T. K. Truong & R. L. Miller, "A new algorithm for computing primitive elements in the field of Gaussian complex integers modulo a Mersenne prime," IEEE Trans. Acoust. Speech Signal Process., v. 27, 1979, pp. 561-563. MR 554962 (81b:10002)
  • [12] G. Drauschke & M. Tasche, "Prime factorizations for values of cyclotomic polynomials in $ \mathbb{Z}[i]$," Arch. Math., v. 49, 1987, pp. 292-300. MR 913159 (89h:11065)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 11A07, 11Y40, 65E05, 94A11

Retrieve articles in all journals with MSC: 11T06, 11A07, 11Y40, 65E05, 94A11

Additional Information

Keywords: Complex number-theoretic transform, complex pseudo Fermat number transform, complex pseudo Mersenne number transform, primitive root of unity modulo m, cyclotomic polynomial
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society