Number-theoretic transforms of prescribed length

Creutzburg, R.; Tasche, M.

doi:10.1090/S0025-5718-1986-0856713-1

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

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
MathSciNet review: 856713
Full-text PDF Free Access

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] Ramesh C. Agarwal and C. Sidney Burrus, Number theoretic transforms to implement fast digital convolution, Proc. IEEE 63 (1975), no. 4, 550–560. MR 0451632 (56 #9914)
[2] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of 𝑏ⁿ±1, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR 715603 (84k:10005)
[3] Reiner Creutzburg and Manfred Tasche, Zahlentheoretische Transformationen und primitive Einheitswurzeln in einem Restklassenring modulo 𝑚, Rostock. Math. Kolloq. 25 (1984), 4–22 (German). MR 763672 (87f:11003a)
[4] 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). 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, and T. K. Truong, Integer convolutions over the finite field 𝐺𝐹(3⋅2ⁿ+1), SIAM J. Appl. Math. 32 (1977), no. 2, 356–365. MR 0506180 (58 #22026)
[7] Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963 (86c:11106)
[8] Peter J. Nicholson, Algebraic theory of finite Fourier transforms, J. Comput. System Sci. 5 (1971), 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] Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, vol. 2, Springer-Verlag, Berlin, 1981. MR 606376 (83e:65219)
[11] J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365–374. MR 0301966 (46 #1120), http://dx.doi.org/10.1090/S0025-5718-1971-0301966-0
[12] Bart Rice, Some good fields and rings for computing number-theoretic transforms, IEEE Trans. Acoust. Speech Signal Process. 27 (1979), no. 4, 432–433. MR 540049 (80h:94005), http://dx.doi.org/10.1109/TASSP.1979.1163258
[13] Bernd Richter, Die Primfaktorzerlegung der Werte der Kreisteilungspolynome, J. Reine Angew. Math. 254 (1972), 123–132 (German). MR 0302620 (46 #1764)