Paper 2026/1546
Note on Number-Theoretic Transforms for Implementers -- Butterflies, Twisting, Incompleteness, and Good's Trick
, Institute of Information Science, Academia SinicaAbstract
We develop the radix-2 number-theoretic transform (NTT) and its butterflies, the twisting trick and why it never changes the transform, the freedom to use Cooley--Tukey butterflies in both directions, incomplete NTTs, Good's trick, and the ways all of these combine---closing with the coefficient-bound bookkeeping that motivates the whole toolkit. This note is intended to help implementers of postquantum cryptography, and is compressed from the author's lecture slides in his Postquantum Cryptography class at National Taiwan University (2020--2025). It may be otherwise trivial for FFT experts who know the DIT--DIF equivalence inside out---except that they tend not to ever encounter incomplete NTTs.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Number Theoretic Transform (NTT)Fast Fourier Transform (FFT)twistingincomplete
- Contact author(s)
- moscito @ as edu tw
- History
- 2026-08-04: last of 2 revisions
- 2026-07-29: received
- See all versions
- Short URL
- https://ia.cr/2026/1546
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1546,
author = {Bo-Yin Yang},
title = {Note on Number-Theoretic Transforms for Implementers -- Butterflies, Twisting, Incompleteness, and Good's Trick},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1546},
year = {2026},
url = {https://eprint.iacr.org/2026/1546}
}
