Number-Theoretic Transforms of Prescribed Length
- 1 October 1986
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 47 (176) , 693-701
- https://doi.org/10.2307/2008183
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.Keywords
This publication has 7 references indexed in Scilit:
- Finite FieldsPublished by Cambridge University Press (CUP) ,1996
- Factorizations of 𝑏ⁿ±1, 𝑏=2, 3, 5, 6, 7, 10, 11, 12 Up to High PowersContemporary Mathematics, 1988
- Some good fields and rings for computing number theoretic transformsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1979
- Number theoretic transforms to implement fast digital convolutionProceedings of the IEEE, 1975
- Die Primfaktorzerlegung der Werte der Kreisteilungspolynome.Journal für die reine und angewandte Mathematik (Crelles Journal), 1972
- Algebraic theory of finite fourier transformsJournal of Computer and System Sciences, 1971
- The Fast Fourier Transform in a Finite FieldMathematics of Computation, 1971