Paper 2022/439

Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms

Hanno Becker
Vincent Hwang
Matthias J. Kannwischer
Lorenz Panny
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× lower than on Cortex-M3.

Available format(s)
Publication info
Published elsewhere. IWSEC 2022
FFT-based multiplication NTT Arm processors RSA
Contact author(s)
hanno becker @ arm com
vincentvbh7 @ gmail com
matthias @ kannwischer eu
lorenz @ yx7 cc
by @ crypto tw
2022-10-22: last of 2 revisions
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.