[2012] Faster arithmetic for number-theoretic transforms

Research References
1

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.

@misc{Harvey2012arxiv,
  author        = {Harvey, David},
  title         = {Faster arithmetic for number-theoretic transforms},
  year          = {2012},
  eprint        = {1205.2926},
  archivePrefix = {arXiv},
  primaryClass  = {cs.MS}
}
Panetière, frequently asked questions
2

Speed up the NTT butterfly, which built on Shoup’s precomputed-quotient modular multiplication, by representing elements of F_p redundantly in [0, 2p) or [0, 4p). Because p < β/4, these values still fit in a machine word, so most conditional corrections can be skipped and a single full reduction is done at the end.

Created together with Claude Opus 5.5 :butterfly::high_voltage: