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 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
[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
Reiner Creutzburg and Manfred Tasche, Zahlentheoretische Transformationen und primitive Einheitswurzeln in einem Restklassenring modulo 𝑚. II, Rostock. Math. Kolloq. 26 (1984), 103–109 (German). MR 778186
[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