Paper 2016/986

Fast Arithmetic Modulo $2^xp^y\pm 1$

Joppe W. Bos and Simon Friedberger


We give a systematic overview of techniques to compute efficient arithmetic modulo $2^xp^y\pm 1$. This is useful for computations in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. One of the main computational bottlenecks in this key-exchange protocol is computing modular arithmetic in a finite field defined by a prime of this special shape. Recent implementations already use this special prime shape to speed up the cryptographic implementations but it remains unclear if the choices made are optimal or if one can do better. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the approaches based on Montgomery multiplication are to be preferred. Furthermore, the outcome of our search reveals that there exist moduli which result in even faster implementations.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
joppe bos @ nxp com
2016-11-03: revised
2016-10-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joppe W.  Bos and Simon Friedberger},
      title = {Fast Arithmetic Modulo $2^xp^y\pm 1$},
      howpublished = {Cryptology ePrint Archive, Paper 2016/986},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.