Welcome to the resource topic for 2024/079
Title:
On Modular Algorithms and Butterfly Operations in Number Theoretic Transform
Authors: Zeyan Yang, Yiran Jia, Guangwu Xu
Abstract: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 of speeding up NTT. We observe that the Chinese remainder theorem (CRT) can be
involved in this type of algorithms in nature and transparent ways.
In this paper, a framework of using CRT to model Montgomery type algorithms is described.
The derivation of these algorithms as well as their correctness are all treated in the CRT framework.
Under our approach,
some problems of a modular reduction algorithm ((published in IACR Transactions on Cryptographic Hardware and Embedded Systems, doi:10.46586/tches.v2022.i4.614-636 )
are identified, and a counterexample is generated to show that the algorithm is incorrect.
ePrint: https://eprint.iacr.org/2024/079
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .