×

Parameter determination for complex number-theoretic transforms using cyclotomic polynomials. (English) Zbl 0675.94002

Let \({\mathbb{Z}}\) and \({\mathbb{Z}}[i]\) denote the ring of integers and Gaussian integers respectively. A number e in \({\mathbb{Z}}[i]\) is called a primitive n-th root of unity \(modulo\quad m\) if \(e^ n\equiv 1 mod m\) and \(GCD(e^ k-1,m)=1\), \(k=1,...,n-1\). The complex number theoretic transform (CNT) of \(length\quad n\) of the n-dimensional vector \(x=(x_ 0,x_ 1,...,x_{n-1})\) is the discrete Fourier transform (DFT) taken \(modulo\quad m\), giving x. The CNT possesses properties resembling those of the DFT, particularly the cyclic convolutional property. Some new results are given here for finding all convenient \(moduli\quad m\) for a CNT with given transform \(length\quad n\) and given primitive n-th root of unity \(modulo\quad m.\)
CNT’s should have the properties: \((i)\quad the\) transform length n should be large enough and highly factorable in order to implement fast algorithms, \((ii)\quad the\) primitive n-th root of unity, e, should have a simple binary representation so that arithmetic \(modulo\quad m\) is easy to perform, \((iii)\quad m\quad should\) be large enough to avoid overflow, small enough so that machine word length is not exceeded and have a simple binary representation. All possible \(moduli\quad m\) for a given \(length\quad n>4\) and given \(e\in {\mathbb{Z}}[i]\) of norm greater than two, are determined via a study of cyclotomic polynomials. The relationship between complex and rational moduli are considered. The question of primitive roots modulo a Mersenne prime, a particularly attractive case for implementation, is also discussed.
Reviewer: I.F.Blake

MSC:

94A11 Application of orthogonal and other special functions
11R04 Algebraic numbers; rings of algebraic integers
11R09 Polynomials (irreducibility, etc.)
42A38 Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of \?\(^{n}\)\pm 1, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. \?=2,3,5,6,7,10,11,12 up to high powers. · Zbl 0527.10001
[2] R. Creutzburg, Finite Signalfaltungen und finite Signaltransformationen in endlichen kommutativen Ringen mit Einselement, Dissertation, Wilhelm-Pieck-Universität Rostock, 1984.
[3] Reiner Creutzburg and Manfred Tasche, \?-Transformation und Faltung in kommutativen Ringen, Elektron. Informationsverarb. Kybernet. 21 (1985), no. 3, 129 – 149 (German, with English and Russian summaries). · Zbl 0585.94003
[4] R. Creutzburg and M. Tasche, Number-theoretic transforms of prescribed length, Math. Comp. 47 (1986), no. 176, 693 – 701. · Zbl 0612.10001
[5] 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. · Zbl 0547.65092 · doi:10.1109/TASSP.1980.1163370
[6] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. · Zbl 0058.03301
[7] 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. · Zbl 0553.10001
[8] Trygve Nagell, Introduction to Number Theory, John Wiley & Sons, Inc., New York; Almqvist & Wiksell, Stockholm, 1951. · Zbl 0042.26702
[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. · Zbl 0376.94002
[10] Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin-New York, 1981. · Zbl 0476.65097
[11] 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. · Zbl 0432.65068 · doi:10.1109/TASSP.1979.1163287
[12] Gabriele Drauschke and Manfred Tasche, Prime factorizations for values of cyclotomic polynomials in \?[\?], Arch. Math. (Basel) 49 (1987), no. 4, 292 – 300. · Zbl 0611.12001 · doi:10.1007/BF01210712
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.