Number-theoretic transforms of prescribed length

Creutzburg, R.; Tasche, M.

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

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.

[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
[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
[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
[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
[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, https://doi.org/10.1137/0132029
[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
[8] Peter J. Nicholson, Algebraic theory of finite Fourier transforms, J. Comput. System Sci. 5 (1971), 524–547. MR 0286905, https://doi.org/10.1016/S0022-0000(71)80014-4
[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-New York, 1981. MR 606376
[11] J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365–374. MR 0301966, https://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, https://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, https://doi.org/10.1515/crll.1972.254.123