# \[2012\] Faster arithmetic for number-theoretic transforms

**URL:** https://collective.flashbots.net/t/2012-faster-arithmetic-for-number-theoretic-transforms/6070
**Category:** References
**Tags:** article
**Created:** [October 5, 2026, 11:56am UTC](https://collective.flashbots.net/t/2012-faster-arithmetic-for-number-theoretic-transforms/6070 "2026-10-05T11:56:31Z")
**Posts on this page:** 2
**Page:** 1

<div class="post-metadata">

### Author: ![guayabyte](https://collective.flashbots.net/user_avatar/collective.flashbots.net/guayabyte/32/4_2.png) [@guayabyte](https://collective.flashbots.net/u/guayabyte)
#### Post date: [October 5, 2026, 11:56am UTC](https://collective.flashbots.net/t/2012-faster-arithmetic-for-number-theoretic-transforms/6070/1 "2026-10-05T11:56:31Z")

</div>

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.

```auto
@misc{Harvey2012arxiv,
  author = {Harvey, David},
  title = {Faster arithmetic for number-theoretic transforms},
  year = {2012},
  eprint = {1205.2926},
  archivePrefix = {arXiv},
  primaryClass = {cs.MS}
}

```

> **[Faster arithmetic for number-theoretic transforms](https://arxiv.org/abs/1205.2926)**
>
> 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...

---

<div class="post-metadata">

### Author: ![guayabyte](https://collective.flashbots.net/user_avatar/collective.flashbots.net/guayabyte/32/4_2.png) [@guayabyte](https://collective.flashbots.net/u/guayabyte)
#### Post date: [October 5, 2026, 11:59am UTC](https://collective.flashbots.net/t/2012-faster-arithmetic-for-number-theoretic-transforms/6070/2 "2026-10-05T11:59:20Z")

</div>

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](https://claude.ai/artifact/D4qweXYWzyZ1dRQmN8zAUu#4cc16542-b243) 🦋⚡