Paper 2022/439

Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms

Hanno Becker, Vincent Hwang, Matthias J. Kannwischer, Lorenz Panny, and Bo-Yin Yang


Conventional wisdom purports that FFT-based integer multiplication methods (such as the Schönhage-Strassen algorithm) begin to compete with Karatsuba and Toom-Cook only for integers of several tens of thousands of bits. In this work, we challenge this belief: Leveraging recent advances in the implementation of Number-Theoretic Transforms (NTT) stimulated by their use in Post-Quantum Cryptography, we report on implementations of NTT-based integer arithmetic on two Arm Cortex-M CPUs on opposite ends of the performance spectrum: Cortex-M3 and Cortex-M55. Our results indicate that NTT-based multiplication is capable of outperforming the big-number arithmetic implementations of popular embedded cryptography libraries for integers as small as 2048 bits. To provide a realistic case study, we benchmark implementations of the RSA encryption and decryption operations. Our cycle counts on Cortex-M55 are about $10\times$ lower than on Cortex-M3.

Available format(s)
Publication info
Preprint. MINOR revision.
FFT-based multiplicationNTTArm processorsRSA
Contact author(s)
hanno becker @ arm com
vincentvbh7 @ gmail com
matthias @ kannwischer eu
lorenz @ yx7 cc
by @ crypto tw
2022-04-15: revised
2022-04-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hanno Becker and Vincent Hwang and Matthias J.  Kannwischer and Lorenz Panny and Bo-Yin Yang},
      title = {Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms},
      howpublished = {Cryptology ePrint Archive, Paper 2022/439},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.