Montgomery curve arithmetic revisited

A one-third century ago, as a means to speed up the elliptic curve method (ECM) for integer factoring, Montgomery suggested using a special elliptic curve form over prime fields and developed an addition chain to compute scalar multiplication on them, which nowadays are famous as Montgomery curves and Montgomery ladder. Kim et al. (http://eprint.iacr.org/2017/669. 2017) and Kim et al. (Adv Math Commun https://doi.org/10.3934/amc.2020090. 2020) found the Montgomery ladder very efficient on every short Weierstrass curve, leading to the most efficient regular scalar multiplication algorithms, which was further improved by Hamburg (https://ches.2017.rump.cr.yp.to/. 2020) and Hamburg (http://eprint.iacr.org/2020/437. 2020). However, the efficiency of the Montgomery ladder in general Montgomery curves remained not improved at all since firstly presented by Montgomery. This paper addresses the long-standing Elliptic Curve Cryptography (ECC) problem. The topic of this article is considered one of the topics that have attracted much attention from the cryptographic community following the launch of a multi-year project called “Post-Quantum Cryptography Standardization" by the National Institute of Standards and Technology (NIST) and also thanks partly to featuring one of the smallest keys of any algorithm known in the literature that is conjectured to be quantum resistant. To the best of our knowledge, this article provides, for the first time after Peter L. Montgomery’s, an improvement of arithmetic in general Montgomery curves, including point doubling and differential addition, which are the most fundamental operations in the context of ECC and supersingular isogeny-based primitives such as Supersingular Isogeny Diffie–Hellman (SIDH) or Supersingular Isogeny Key Encapsulation (SIKE), as well as ECM.