Parameter determination for complex number-theoretic transforms using cyclotomic polynomials

Creutzburg, R.; Tasche, M.

doi:10.1090/S0025-5718-1989-0946602-9

Parameter determination for complex number-theoretic transforms using cyclotomic polynomials
HTML articles powered by AMS MathViewer

by R. Creutzburg and M. Tasche PDF

Math. Comp. 52 (1989), 189-200 Request permission

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

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

Finite Signalfaltungen und finite Signaltransformationen in endlichen kommutativen Ringen mit Einselement

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
R. Creutzburg and M. Tasche, Number-theoretic transforms of prescribed length, Math. Comp. 47 (1986), no. 176, 693–701. MR 856713, DOI 10.1090/S0025-5718-1986-0856713-1
Eric Dubois and Anastasios N. Venetsanopoulos, The generalized discrete Fourier transform in rings of algebraic integers, IEEE Trans. Acoust. Speech Signal Process. 28 (1980), no. 2, 169–175. MR 563379, DOI 10.1109/TASSP.1980.1163370
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. MR 0067125
James H. McClellan and Charles M. Rader, Number theory in digital signal processing, Prentice Hall Signal Processing Series, Prentice Hall, Inc., Englewood Cliffs, NJ, 1979. Including reprinted papers. MR 723867
Trygve Nagell, Introduction to Number Theory, John Wiley & Sons, Inc., New York; Almqvist & Wiksell, Stockholm, 1951. MR 0043111

IEEE Trans. Acoust. Speech Signal Process.

Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. MR 606376
I. S. Reed, T. K. Truong, and 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. 27 (1979), no. 5, 561–563. MR 554962, DOI 10.1109/TASSP.1979.1163287
Gabriele Drauschke and Manfred Tasche, Prime factorizations for values of cyclotomic polynomials in $\textbf {Z}[i]$, Arch. Math. (Basel) 49 (1987), no. 4, 292–300. MR 913159, DOI 10.1007/BF01210712