On Modular Algorithms and Butterfly Operations in Number Theoretic Transform

ePrint Report: On Modular Algorithms and Butterfly Operations in Number Theoretic Transform

Zeyan Yang, Yiran Jia, Guangwu Xu

Number theoretic transform (NTT) has been a very useful tool in computations for number theory, algebra and cryptography.
Its performance affects some post-quantum
cryptosystems. In this paper, we discuss the butterfly operation of NTT. This basic module of NTT requires heavy modular
arithmetics. Montgomery reduction is commonly used in this setting. Recently several variants of Montgomery have been proposed
for the purpose …

algebra algorithms cryptography discuss eprint report modular ntt operations performance post-quantum quantum report theory tool transform