Faster arithmetic for number-theoretic transforms
classification
💻 cs.SC
cs.DS
keywords
arithmeticmodulotransformsbasiccomputationdecreasingeffectefficiency
read the original abstract
We show how to improve the efficiency of the computation of fast Fourier transforms over F_p where p is a word-sized prime. Our main technique is optimisation of the basic arithmetic, in effect decreasing the total number of reductions modulo p, by making use of a redundant representation for integers modulo p. We give performance results showing a significant improvement over Shoup's NTL library.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.