Montgomery curves and their arithmetic

Craig Costello (1) , Benjamin Smith (2, 3)

1 Microsoft Research [Redmond]
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 GRACE - Geometry, arithmetic, algorithms, codes and encryption

Three decades ago, Montgomery introduced a new elliptic curve model for use in Lenstra's ECM factorization algorithm. Since then, his curves and the algorithms associated with them have become foundational in the implementation of elliptic curve cryptosystems. This article surveys the theory and cryptographic applications of Montgomery curves over non-binary finite fields, including Montgomery's x-only arithmetic and Ladder algorithm, x-only Diffie–Hellman, y-coordinate recovery, and 2-dimensional and Euclidean differential addition chains such as Montgomery's PRAC algorithm.

Mots clés: Elliptic curve scalar multiplication; Elliptic curve cryptography; Montgomery curves; Montgomery ladder; Elliptic curve method; Addition chains

Domaines: Cryptographie et sécurité [cs.CR]; Théorie des nombres [math.NT]

Craig Costello, Benjamin Smith. Montgomery curves and their arithmetic: The case of large characteristic fields. Journal of Cryptographic Engineering, 2017, Special issue on Montgomery arithmetic, ⟨10.1007/s13389-017-0157-6⟩. ⟨hal-01483768⟩