Paper 2026/2366
Multiplying Not-So-Big Integers with FFTs: Finding and Pushing the Crossover on Large Modern OoO ARM CPUs
, IIS and CITI, Academia Sinica, IIS and CITI, Academia SinicaAbstract
Established multiple-precision software generally reserves Fast-Fourier Transform (FFT) multiplication for very large operands; for example, GMP reports full-product FFT thresholds of roughly 3000--10000 limbs. Becker et al. showed that Number-Theoretic Transform (NTT) multiplication can become advantageous much earlier on Cortex-M microcontrollers. It thus becomes an interesting engineering question to check where the crossover actually takes place on a big modern CPU. Our first-generation implementation on Cortex-A76 and Neoverse-N1 shows that the crossover point is around 10k bits when using ARMv8+ with Neon, using optimized and verified code. Motivated by the tighter Barrett bound of Becker, we developed the Second implementation, which eliminates additional reductions and pushes the crossover below 5.6k bits. We integrate our multipliers into OpenSSL RSA, resulting in end-to-end speedup for the public-key operations.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Fast Fourier TransformBig Integer MultiplicationsUnsaturated Limbs
- Contact author(s)
-
cesarehuang @ icloud com
daisyliu0225 @ gmail com
b12902036 @ ntu edu tw
bywang @ iis sinica edu tw
byyang @ iis sinica edu tw - History
- 2026-10-07: approved
- 2026-10-05: received
- See all versions
- Short URL
- https://ia.cr/2026/2366
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2366,
author = {Cesare Huang and Daisy Meng-Wei Liu and David Shu-Yu Wu and Bow-Yaw Wang and Bo-Yin Yang},
title = {Multiplying Not-So-Big Integers with {FFTs}: Finding and Pushing the Crossover on Large Modern {OoO} {ARM} {CPUs}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2366},
year = {2026},
url = {https://eprint.iacr.org/2026/2366}
}
