Faster arithmetic for number-theoretic transforms

作者：David Harvey · 发表于：Journal of symbolic computation · 年份：2012 · DOI：10.1016/j.jsc.2013.09.002 · 被引用次数：106 · 研究领域：Computer Science、Mathematics

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 [email protected]?s NTL library.